[백준] 🥇 1987 알파벳 [BFS에 대한 고찰]

📌 난이도

🥇 Gold 4

📌 문제

https://www.acmicpc.net/problem/1987

📌 BFS로 풀 수 없는 이유

갈수 있는 방향이 이전 방향을 제외하고 최대 3방향이고, 알파벳의 개수인 26개만큼 깊게 들어간다.
따라서, DFS에서 깊이가 26인 지점의 개수만큼 BFS에서는 Queue에 다음 위치정보가 들어가게 되는데 이 값이 다음 코드의 결과값과 같다.

public class Test {
    static final int[] DR = {-1, 0, 1, 0};
    static final int[] DC = {0, 1, 0, -1};
    static long count = 0;
    static int N = 20;
    static boolean visited[][];

    public static void main(String[] args) throws IOException {
        visited = new boolean[N][N];

        DFS(0, 0, 1);

        System.out.println(count);
    }

    static void DFS(int r, int c, int depth) {
        if (depth == 26) {
            count++;
            return;
        }

        visited[r][c] = true;

        for (int i = 0; i < DR.length; i++) {
            int nextR = DR[i] + r;
            int nextC = DC[i] + c;
            if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= N) continue;

            if (!visited[nextR][nextC]) {
                DFS(nextR, nextC, depth + 1);
            }
        }

        visited[r][c] = false;
    }
}

📌 BFS가 실재로는 가능한 이유

하지만, 이전에 다녀왓던 곳들의 알파벳들만 동일하다면, 심지어 다녀왓던 순서가 다르더라도 현재 지점에서의 다녀온 정점들의 알파벳이 동일하다면, 그 지점에서 여러번 BFS를 돌릴 필요가 없이 다른 BFS는 제외가 가능하다. ( BFS에 백트래킹 응용 )

위의 1번 그림에서 G에 도달하는 방법은 여러가지이지만, 결국 G라는 정점에서 다녀온 알파벳은 ( A, B, C, D, E, F, G ) 이므로, 다녀온 경로에 상관없이 동일하게 D로는 못가고, H쪽으로만 갈 수 있다.

또한 위의 2번 그림에서 I에 도달하는 방법은 여러가지이고, 심지어 들어가는 알파벳의 순서조차도 다르지만 I라는 정점에 도달하는 순간, 이전의 알파벳이 동일하다면, 모두 같은 방법으로 도달한 것과 마찬가지가 되게 된다.

따라서, BFS와 같은 방식으로 구현을 할 때, Queue를 이용하여 구현하는 것이 아닌, LinkedHashSet에 ( int CurR, int CurC, boolean[ ] ) 와 같은 방법으로 구현을 하면, 오히려 DFS로 구현을 하는 방식보다도 더 빠른 동작시간이 나오는 코드 구현이 가능할 것 같다.

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁