[Programmers] 단어변환

[작성일]

• 2022-02-17

[분류]

• dfs
  
  
  

[문제링크]

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

[요구사항]

• 몇 단계를 거쳐 begin을 target으로 변환할 수 있는지 출력하라.
  
  
  

[풀이]

전형적인 dfs 문제이다. 있는 알파벳 중에 하나를 선택하고 알파벳 하나만 다르면 계속 이동하는 식으로 해서 최종 target까지 도착하면 답으로 판단하고 그 까지 걸린 횟수를 갱신해준다.

[코드]

class Solution {
    // dfs
    int ans = 99999999;
    public int solution(String begin, String target, String[] words) {
        // words안에 target없을 경우 return 0
        boolean check = false;
        for(String word : words) {
            if(target.equals(word)) {
                check = true;
                break;
            } 
        }
        if(!check) return 0;
    
        boolean[] visited = new boolean[words.length];
        for(int i = 0; i < words.length; i++) {
            // 조건에 맞는가 - 방문 안했고, 하나만 바꾸고, 
            if(isDifferentOne(words[i], begin)) {
                // 간다
                dfs(i, 1, visited, words, target);
            }
        }
        
        return ans;
    }
    
    public void dfs(int now, int depth, boolean[] visited, String[] words, String target) {
        // 목적지인가
        if(target.equals(words[now])) {
            ans = Math.min(ans, depth);
            return;
        }
        
        if(depth == words.length) return;
        
        // 순회
        for(int i = 0; i < words.length; i++) {
            // 조건에 맞는가 - 방문 안했고, 하나만 바꾸고, 
            if(!visited[i] && isDifferentOne(words[i], words[now])) {
                // 간다
                visited[i] = true;
                dfs(i, depth + 1, visited, words, target);
                visited[i] = false;
            }
        }
    }
    
    public boolean isDifferentOne(String a, String b) {
        int gap = 0;
        for(int i = 0; i < a.length(); i++) {
            if(a.charAt(i) == b.charAt(i)) continue;
            gap++;
        }
        return gap == 1 ? true: false;
    }
}

[느낀점]

무난한 dfs 문제였다.