[Programmers] 단어 변환 - Java

Level 3

코딩테스트 연습 - 단어 변환

 

문제 풀이

DFS 문제 

 

우선 문제에서 주어진 조건대로 철자 하나씩만 바꿔야하기 때문에 두개이상 달라지면 false를 반환하는 함수를 만들어줬다. 

그리고 재귀함수에서 한개만 달라지는지 확인하고 그게 맞으면 방문처리하는 식으로 dfs를 구현했다.

 

몇 개의 단계를 거쳤는지 확인하기 위해 stage 변수를 만들고 target과 같게되면 바로 최소값과 비교해 저장한다.

 

여기서 주의해야 할 것은 그냥 "=="연산자로 문자열을 비교하면 안된다는 것! 주소값이 다르면 다르다고 반환하기 때문에 String 클래스의 equals메서드를 이용해야 같은 문자열인지 알 수 있다.

 

코드

class Solution {
    public int min = 9999999;

    public void dfs(String begin, String target, String[] words, int stage, int[] visited) {
        if (target.equals(begin)) {
            if (stage < min) {
                min = stage;
            }
            return;
        }

        for (int i=0; i<words.length; i++) {
            if(checkWords(begin, words[i]) && visited[i] == 0) {
                visited[i] = 1;
                dfs(words[i], target, words, stage + 1, visited);
                visited[i] = 0;
            }
        }

    }

    public boolean checkWords(String checkWord1, String checkWord2) {
        boolean check = false;

        for (int i = 0; i < checkWord1.length(); i++) {
            char a = checkWord1.charAt(i);
            char b = checkWord2.charAt(i);

            if (a!=b) {
                if (check) return false;
                check = true;
            }
        }
        return true;
    }

    public int solution(String begin, String target, String[] words) {
        int[] visited = new int[words.length];
        dfs(begin, target, words, 0, visited);

        if (min == 9999999) return 0;
        else return min;
    }
}