[프로그래머스] 43163 단어 변환(Lv.3) - DFS

문제

단어 변환

코드

• 비슷한 유형의 문제: 촌수계산
• 풀이 방법

1. 한 번에 한 개의 알파벳만 바꿀 수 있기 때문에 words를 순회하며 현재 단어와 한 개의 알파벳만 다르고 나머지 알파벳이 같은 단어를 찾아서 dfs을 실행한다.
2. target에 도달한 경우 다른 경로의 단계와 비교하여 더 적은 단계의 과정을 거쳤다면 result에 저장한다.
3. 최소 단계가 저장된 result를 반환한다.

import java.util.Objects;

class Solution {
    static int result = Integer.MAX_VALUE;
    public int solution(String begin, String target, String[] words) {
        // 변환할 수 없는 경우
        int cnt = 0;
        for (String word : words) {
            if (Objects.equals(word, target)) cnt++;
        }
        if (cnt == 0) return 0;

        boolean[] visited = new boolean[words.length];

        dfs(words, visited, begin, target, 0);
        return result;
    }

    public void dfs(String[] words, boolean[] visited, String nowWord, String target, int cost) {
        // target에 도달한 경우 다른 경로와 비교하여 더 적은 단계의 과정을 거쳤다면 result에 저장
        if (Objects.equals(nowWord, target)) {
            result = Math.min(result, cost);
            return;
        }
        for (int i = 0; i < words.length; i++) {
            int cnt = 0;
            if (!visited[i]) {
                // 현재 단어와 한 개의 알파벳만 다르고 나머지 알파벳이 같은 단어를 찾기
                for (int j = 0; j < nowWord.length(); j++) {
                    if (words[i].charAt(j) == nowWord.charAt(j)) cnt++;
                }
                // 한 개의 알파벳만 다른 단어일 경우 dfs 실행
                if (cnt == nowWord.length() - 1 && !visited[i]) {
                    visited[i] = true;
                    dfs(words, visited, words[i], target, cost + 1);
                    visited[i] = false;
                }
            }
        }
    }
}

 

Queue를 이용한 풀이

큐를 이용한 풀이도 가능하다. 재귀 대신 큐를 사용했다는 점을 제외하면 나머지 로직은 동일하다.

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = 0;

        Queue<String> q = new LinkedList<>();
        int[] ch = new int[words.length]; 
        q.offer(begin); 
        int level = 0; 

        while(!q.isEmpty()) {
            int size = q.size(); 

            for(int t = 0; t < size; t++) {
                String tmp = q.poll(); 
                if(tmp.equals(target)) return level; 

                char[] a = tmp.toCharArray(); 

                for(int i = 0; i < words.length; i++) {
                    char[] b = words[i].toCharArray(); 
                    int cnt = 0; 
                    for(int j = 0; j < b.length; j++) {
                        if(a[j] != b[j]) cnt++; 
                    }

                    if(cnt == 1 && ch[i] == 0) {
                         q.offer(words[i]); 
                        ch[i] = 1; 
                    }
                }
            }

            level++; 
        }  

        return answer;
    }
}