[코딩테스트] - 단어 변환 LV3 ( 프로그래머스(programmers) / java )👍

안녕하세요 나홀로전세집입니다.

오늘은 레벨3! 단어 변환을 풀어보겠습니다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/43163

프로그래머스

 

 

• 단어 변환

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

 

문제는 시작 단어 begin을 받고 바꿔야 하는 단어 target을 받은 후 begin을 words 배열에 있는 단어로 한 글자 씩 바꾸는 최솟 값을 구하는 문제입니다.

 

이번에 dfs 문제를 한번 풀어보고, 이해가 제대로 됐는지 다시한번 dfs 문제를 풀어보게 되었습니다.

 

 

 

void dfs(String word, int step) {
		if (word.equals(target)) {
			min = Math.min(min, step);
			return;
		}
		for (int i = 0; i < words.length; i++) {
			if (visit[i] == 0 && diffrent_Check(word, words[i])) {
				visit[i] = 1;
				dfs(words[i], step + 1);
				visit[i] = 0;
			}
		}
	}

제가 짠 dfs 메서드 코드입니다.

매개변수로 단어 word와 몇 번 했는지 세어주는 step 을 사용했습니다.

종료 조건으로는 target과 변화하는 word 값이 같아지면 종료하도록 만들었습니다.



실행 방식은 visit이라는 방문 배열을 확인하여 방문하지 않았고,(visit 배열의 값이 0일 때) 단어와 다른 문자의 개수가 1개인지 확인해 주는 diffrent_Check 메서드를 실행시켜줬습니다. 만약 다른 문자의 개수가 1개이고, 방문을 안 했던 곳이면 재귀 호출을 통해 dfs를 다시 한번 실행해 주는 방법으로 만들었습니다. return 되었을 때는 다시 방문을 하지 않은 것과 같기 때문에 visit의 값을 0으로 초기화 시켜줬습니다.

 

 

한번 dfs 문제를 풀어보니 어떤 방향으로 나아가야 할지 감을 잡게 되었습니다. 다음 목표는 bfs 문제를 푸는 것으로 잡아야겠습니다. 감사합니다.

 

 

 

전체코드

class Solution {
	String begin;
	String target;
	String[] words;
	int[] visit;
	int min;

	public int solution(String begin, String target, String[] words) {
		this.begin = begin;
		this.target = target;
		this.words = words;
		visit = new int[words.length];
		int difcount = 0;

		min = words.length;

		for (int i = 0; i < words.length; i++) {
			if (target.equals(words[i])) {
				difcount++;
			}
		}
		if (difcount == 0) {
			return 0;
		}
		
		dfs(begin, 0);

		return min;
	}

	void dfs(String word, int step) {
		if (word.equals(target)) {
			min = Math.min(min, step);
			return;
		}
		for (int i = 0; i < words.length; i++) {
			if (visit[i] == 0 && diffrent_Check(word, words[i])) {
				visit[i] = 1;
				dfs(words[i], step + 1);
				visit[i] = 0;
			}
		}
	}

	boolean diffrent_Check(String word1, String word2) { // 한개만 다른지 체크하는 메소드
		int diffrent_Count = 0; // 두 String의 다른만큼 카운트 해주는 변수
		for (int i = 0; i < word1.length(); i++) {
			if (word1.charAt(i) != word2.charAt(i)) {
				diffrent_Count++;
				if (diffrent_Count > 1) { // 한개 이상으로 다를 때
					return false; // 할 수 없다
				}
			}
		}
		return diffrent_Count == 1;
	}
}

 

 

오늘도 즐코딩 하시고 좋은 하루 되세요~