[프로그래머스]단어 변환 / 자바 (BFS/DFS 맛꿀마 문제)

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

프로그래머스

---

이 문제는 DFS와 BFS 모두 풀이가 가능한 문제입니다.

 

먼저 문제의 요구사항을 살펴보면, 문자열 begin으로부터 문자열 target까지의 변환에 필요한 최소 변환 횟수를 구하는 것이 목표입니다.

단, 변환 조건은 한 번에 한 개의 알파벳만 변환이 가능하다는 겁니다. 즉, A에서 B로의 변환이 가능한 경우는 A와 B를 비교했을 때 한 글자를 제외하고 나머지 글자가 모두 같은 경우라고 생각할 수 있습니다.

이제 각각의 방식을 알아보도록 하겠습니다.

1. BFS

먼저 BFS입니다. 이 문제를 처음 접했을 때 제가 먼저 시도한 접근법인데요. 제 경우에 DFS는 재귀형식이라 직관적인 이해가 어려워서인지 보통 BFS로의 접근법을 먼저 생각하게 되는 경향이 있더라구요.

 

BFS에서의 중요한 역할을 하는 것은 방문체크를 하는 visited[] 배열과 탐색할 문자열의 인덱스를 저장할 que 입니다.

canConvert() 메서드를 활용하여 변환이 가능한 문자열의 인덱스를 que에 넣으며 가까운 아이템부터 순차적으로 탐색합니다.

탐색한 문자열의 인덱스에 대해서는 재방문으로 인한 무한루프에 빠지는 것을 방지하기 위해 방문체크를 해줍니다. 이를 활용하여 que에 아이템을 삽입하기 전에 방문 여부를 확인하여 방문되지 않은 아이템에 대해서만 삽입을 해주는 것입니다.

 

그리고 while 문을 사용하는 부분은 cnt의 크기별로 탐색을 하도록 이중 while 문 구조를 택하였습니다.

이로써 시작 노드로부터 같은 거리의 있는 모든 인접 노드를 탐색하고 cnt를 늘려준 뒤 그 다음 거리를 탐색할 수 있습니다.

(이 부분은 문자열의 인덱스와 cnt 정보를 함께 가지는 커스텀 클래스를 정의하여 이 클래스의 객체를 que에 넣는 식으로도 구현할 수 있겠습니다.)

 

마지막으로 while 문에서 target을 만나지 못한 경우 target으로의 변환이 불가능하기 때문에 0을 반환하도록 하였습니다.

 

Java 코드

class Solution_BFS {
    public int solution(String begin, String target, String[] words) {
        boolean[] visited = new boolean[words.length];
        Queue<Integer> que = new LinkedList<>();
		
        // 첫번째로 변환할 문자열의 인덱스를 que에 삽입
        for (int i = 0; i < words.length; i++) {
            String str = words[i];
            if (canConvert(begin, str)) {
                visited[i] = true;
                que.add(i);
                break;
            }
        }

        int cnt = 1;
        while (!que.isEmpty()) {
            int size = que.size();
            while (size-- > 0) {
                String cur = words[que.poll()];

                if (cur.equals(target)) {
                    return cnt;
                }

                for (int i = 0; i < words.length; i++) {
                    if (visited[i]) continue;

                    String str = words[i];
                    if (canConvert(cur, str)) {
                        visited[i] = true;
                        que.add(i);
                    }
                }
            }
            cnt++;
        }

        return 0;
    }

    /**
     * from 문자열에서 to 문자열로의 변환이 가능한지 여부를 반환하는 메서드
     */
    public boolean canConvert(String from, String to) {
        int cnt = 0;
        for (int i = 0; i < from.length(); i++) {
            if (from.charAt(i) == to.charAt(i)) cnt++;
        }

        return from.length() == cnt+1 ? true : false;
    }
}

 

2. DFS

다음으로는 DFS 입니다.

코드를 작성해놓고 보니 코드 자체는 BFS보다 간결해보이네요. DFS 접근 방식은 기본적으로 재귀 함수의 형태를 띱니다. solution() 메서드의 매개변수로 주어진 데이터들을 DFS에서 그대로 이어받으면서 여기에 추가적으로 변환횟수를 나타내는 cnt 변수를 가집니다. 한 depth 더 깊어질 때마다 cnt+1를 하는 방식으로 횟수를 늘려가는 방식입니다.

 

여기에도 마찬가지로 visited[] 배열을 통해 방문체크를 하는데 주의할 점은 DFS() 메서드를 호출 앞과 뒤에서 visited[] 배열의 상태를 적절히 변환해주어야 한다는 것입니다. 이로써 탐색의 경로 간에 서로 간섭이 생기는 경우를 방지할 수 있습니다. 

class Solution_DFS {
    public boolean[] visited;
    public int answer = 0;

    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];
        DFS(begin, target, words, 0);

        return answer;
    }

    public void DFS(String cur, String target, String[] words, int cnt) {
        if (cur.equals(target)) {
            answer = cnt;
            return;
        }

        for (int i = 0; i < words.length; i++) {
            if (visited[i]) continue;

            if (canConvert(cur, words[i])) {
                visited[i] = true;
                DFS(words[i], target, words, cnt+1);
                visited[i] = false;
            }
        }
    }

    /**
     * from 문자열에서 to 문자열로의 변환이 가능한지 여부를 반환하는 메서드
     */
    public boolean canConvert(String from, String to) {
        int cnt = 0;
        for (int i = 0; i < from.length(); i++) {
            if (from.charAt(i) == to.charAt(i)) cnt++;
        }

        return from.length() == cnt+1 ? true : false;
    }

}