99클럽 코테 스터디 14일차 TIL: [프로그래머스] 단어 변환

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

프로그래머스

 

처음에는 익숙한 dfs로 풀었었는데, begin을 target으로 변환하는 가장 빠른 과정을 찾아야 하므로 bfs가 더 적합한 거 같다. 그런데 dfs로 풀더라도 가지치기를 하면 되니까 큰 차이는 없을 거 같다. 

 

dfs로 푼 풀이는 다음과 같다.

import java.util.*;

class Solution {
    
    String begin;
    String target;
    String[] words;
    boolean[] visited;
    int answer = Integer.MAX_VALUE;
    
    public int solution(String begin, String target, String[] words) {
        this.begin = begin;
        this.target = target;
        this.words = words;
        visited = new boolean[words.length];
        
        dfs(begin, 0);
        
        return answer == Integer.MAX_VALUE ? 0 : answer;
    }
    
    public void dfs(String now, int cnt) {  
        if (cnt > answer) return; // 가지치기
        
        if (now.equals(target)) {
            answer = Math.min(answer, cnt);
            return;
        }
        
        for (int i = 0; i < words.length; i++) {
            if (!visited[i] && canConvert(now, words[i])) {
                visited[i] = true;
                dfs(words[i], cnt + 1);
                visited[i] = false;
            }
        }
    }
    
    public boolean canConvert(String str1, String str2) {
        int diff = 0;
        for (int i = 0; i < str1.length(); i++) {
            if (str1.charAt(i) != str2.charAt(i)) diff++;
        }
        
        return diff == 1;
    }
}

 

bfs로 푼 풀이는 다음과 같다.

import java.util.*;

class Solution {
    
    String begin;
    String target;
    String[] words;
    boolean[] visited;
    int answer;
    
    public int solution(String begin, String target, String[] words) {
        this.begin = begin;
        this.target = target;
        this.words = words;
        visited = new boolean[words.length]; 
        
        // bfs
        Queue<Node> que = new LinkedList<>();
        que.add(new Node(begin, 0));
        
        while (!que.isEmpty()) {
            Node now = que.poll();
            if (now.str.equals(target)) {
                answer = now.cnt;
                break;
            }
            
            for (int i = 0; i < words.length; i++) {
                if (visited[i]) {
                    continue;
                }
                if (canConvert(now.str, words[i])) {
                    que.add(new Node(words[i], now.cnt + 1));
                    visited[i] = true;
                }
            }
        }
        
        return answer;
    }
    
    public boolean canConvert(String str1, String str2) {
        int diff = 0;
        for (int i = 0; i < str1.length(); i++) {
            if (str1.charAt(i) != str2.charAt(i)) diff++;
        }
        
        return diff == 1;
    }
    
    public class Node {
        
        String str;
        int cnt; // str까지 오는데 걸린 변환 횟수
        
        public Node(String str, int cnt) {
            this.str = str;
            this.cnt = cnt;
        }
    }
}