DFS/BFS - 단어 변환

프로그래머스 문제인 '단어 변환'을 해결해 봅시다.

문제를 먼저 살펴보도록 할게요.

 

문제 설명

 

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

 

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.

2. words에 있는 단어로만 변환할 수 있습니다.

 

예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

 

구글의 도움을 많이 받아 해결할 수 있었습니다 🤣 

DFS를 사용했는데, 다른 사람들의 풀이를 보니 BFS로도 많이 풀었길래 기록할겸 정리해두겠습니다.

 

 

import java.util.regex.Pattern;
class Solution {

    int dfs(String begin, String target, int index, boolean visited[], String[] words, int cnt) {
        if (begin.equals(target))
            return cnt;

        if (visited[index])
            return cnt;

        visited[index] = true;

        int ans = 0;
        for (int i = 0; i < words.length; i++) {
            if (index != i && isOneDiffer(begin, words[i]) && !visited[i]) {
                ans = dfs(words[i], target, i, visited, words, cnt + 1);
            }
        }
        return ans;
    }

    boolean isOneDiffer(String base, String com) {
        for (int i = 0; i < base.length(); i++) {
            StringBuilder beginRegex = new StringBuilder(base);
            beginRegex.setCharAt(i, '.');
            if (Pattern.matches(beginRegex.toString(), com))
                return true;
        }
        return false;
    }
    
    public int solution(String begin, String target, String[] words) {
		int v = words.length + 1;
        int answer = v;

        for (int i = 0; i < words.length; i++) {
            boolean[] visited = new boolean[v];
            if (isOneDiffer(begin, words[i]))
                answer = Math.min(answer, dfs(words[i], target, i, visited, words, 1));
        }
        return answer;
    }
}

 

먼저 begin에서 바꿀 수 있는 단어들을 (한 글자만 다른 것들 = isOneDiffer) 모두 확인합니다.

만약, 바꿀 수 있는 단어면 dfs 메소드를 실행하게 되고, target과 동일한 단어가 나올 때까지 재귀합니다.

 

단어를 찾을 때마다 cnt (count)는 증가하게 되고, ans (answer)이 최종값을 담아냅니다.

 

 

🔥 BFS 

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.regex.Pattern;

class Solution {
    class Node {
        String next;
        int edge;

        public Node(String next, int edge) {
            this.next = next;
            this.edge = edge;
        }
    }

    public int solution(String begin, String target, String[] words) {
        int answer = 0;
        Queue<Node> q = new LinkedList<>();

        boolean[] isAdd = new boolean[words.length];
        q.add(new Node(begin, 0));


        while(!q.isEmpty()) {
            Node n = q.poll();

            if (n.next.equals(target)) {
                answer = n.edge;
                break;
            }

            for (int i =0; i< words.length; i++) {
                if (!isAdd[i] && isOneDiffer(n.next, words[i])) {
                    isAdd[i] = true;
                    q.add(new Node(words[i], n.edge+1));
                }
            }
        }

        return answer;
    }


    boolean isOneDiffer(String base, String com) {
        for (int i = 0; i < base.length(); i++) {
            StringBuilder beginRegex = new StringBuilder(base);
            beginRegex.setCharAt(i, '.');
            if (Pattern.matches(beginRegex.toString(), com))
                return true;
        }
        return false;
    }
}

 

Queue에 Node를 타입으로 지정해서 begin과 같은 단어가 있다면, 모두 찾아서 queue에 추가합니다. 

그 이후부터는 BFS 로직과 동일합니다.