(프로그래머스) 단어 변환

지니·2021년 6월 27일
0

알고리즘

목록 보기
9/33

문제

두 개의 단어 begin, target과 단어의 집합 words가 있을 때

begin = "hit"
target = "cog"
words = ["hot","dot","dog","lot","log","cog"]

"hit" -> "hot" -> "dot" -> "dog" -> "cog"

이처럼 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 할 때 최소의 단계를 찾는 문제다.
(단, 모든 단어의 길이는 같으며 변환 방법이 없으면 0을 반환한다.)


접근

보자마자 DFS로 풀 생각부터 했다. 어차피 전부 뒤져야 하기 때문에 전처리는 따로 하지 않았다.


코드

class Solution {
    String target;
    String[] words; 
    boolean[] visited; // 단어 방문 여부
    int answer = 0;
    
    public int solution(String begin, String target, String[] words) {
        this.words = words;
        this.target = target;
        visited = new boolean[words.length];
        
        dfs(begin, 0);
        return answer;
    }
    
    public void dfs(String str, int cnt) {
        if (str.equals(target) && (answer == 0 || answer > cnt)) {
            answer = cnt;
            return;
        }
        
        for (int i = 0; i < words.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                
                String word = words[i];
                int diff = 0; // 글자 차이
            
                for (int j = 0; j < word.length(); j++) {
                    if (str.charAt(j) != word.charAt(j)) {
                        diff++;
                    
                        if (diff >= 2) {
                            break;
                        }
                    }
                
                    if (j == word.length() - 1 && diff == 1) {
                        dfs(word, cnt + 1);
                    }
                }
                
                visited[i] = false;
            }
        }
    }
}

깜빡하지 않도록 하기 위한 추가적인 메모

  • DFS 문제를 풀 때 방문한 정점을 재방문하면 무한루프가 돌게 된다.
    반드시 특정 정점을 방문했는지 체크하는 과정을 잊지 말자.
  • 현재 정점과 인접한 지점을 모두 탐색했으면 본인 정점에 대한 방문 여부를 다시 미방문으로 풀어줘야 한다.
    (본인 정점이 나중에 다른 정점으로부터 인접한 정점일 가능성이 있기 때문이다.)
profile
Coding Duck

0개의 댓글

Powered by GraphCDN, the GraphQL CDN