[Java]백준 1987 - 알파벳

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

최초 코드 - 메모리 초과 발생

import java.util.*;
import java.io.*;

class Main {
    private static int[] dy = {1, 0, -1, 0};
    private static int[] dx = {0, 1, 0, -1};
    private static char[][] grid;
    private static int R;
    private static int C;
    private static int answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] RC = br.readLine().split(" ");
        R = Integer.parseInt(RC[0]);
        C = Integer.parseInt(RC[1]);

        grid = new char[R][C];

        for (int i = 0; i < R; i++) {
            grid[i] = br.readLine().toCharArray();
        }

        bfs();
        System.out.println(answer);
    }

    private static void bfs() {
        Queue<Status> q = new LinkedList<>();
        q.offer(new Status(0, 0, new HashSet<>(List.of(grid[0][0]))));

        while (!q.isEmpty()) {
            Status polled = q.poll();
            answer = Math.max(answer, polled.history.size());
            for (int k = 0; k < 4; k++) {
                int _y = polled.y + dy[k];
                int _x = polled.x + dx[k];
                if (isValidCoord(_y, _x) && !polled.history.contains(grid[_y][_x])) {
                    HashSet<Character> newSet = new HashSet<>(polled.history);
                    newSet.add(grid[_y][_x]);
                    q.offer(new Status(_y, _x, newSet));
                }
            }
        }
    }

    private static boolean isValidCoord(int y, int x) {
        return 0 <= y && y < R && 0 <= x && x < C;
    }

    static class Status {
        int y;
        int x;
        Set<Character> history;

        Status(int y, int x, Set<Character> history) {
            this.y = y;
            this.x = x;
            this.history = history;
        }
    }
}

두번째 코드 - DFS 풀이 (정답)

import java.io.*;

class Main {
    private static final boolean[] visited = new boolean[26];
    private static char[][] grid;
    private static int R;
    private static int C;
    private static int answer;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] RC = br.readLine().split(" ");
        R = Integer.parseInt(RC[0]);
        C = Integer.parseInt(RC[1]);

        grid = new char[R][C];

        for (int i = 0; i < R; i++) {
            grid[i] = br.readLine().toCharArray();
        }

        visited[grid[0][0]-65]=true;
        dfs(0, 0, 1);
        System.out.println(answer);
    }

    private static void dfs(int row, int col, int depth) {
        answer = Math.max(answer, depth);
        //상
        if (isValidCoord(row - 1, col)) {
            int idx = grid[row - 1][col] - 65;
            if (!visited[idx]) {
                visited[idx] = true;
                dfs(row - 1, col, depth + 1);
                visited[idx] = false;
            }
        }
        //하
        if (isValidCoord(row + 1, col)) {
            int idx = grid[row + 1][col] - 65;
            if (!visited[idx]) {
                visited[idx] = true;
                dfs(row + 1, col, depth + 1);
                visited[idx] = false;
            }
        }
        //좌
        if (isValidCoord(row, col - 1)) {
            int idx = grid[row][col - 1] - 65;
            if (!visited[idx]) {
                visited[idx] = true;
                dfs(row, col - 1, depth + 1);
                visited[idx] = false;
            }
        }
        //우
        if (isValidCoord(row, col + 1)) {
            int idx = grid[row][col + 1] - 65;
            if (!visited[idx]) {
                visited[idx] = true;
                dfs(row, col + 1, depth + 1);
                visited[idx] = false;
            }
        }
    }

    private static boolean isValidCoord(int y, int x) {
        return 0 <= y && y < R && 0 <= x && x < C;
    }
}

개선 코드 - dy, dx배열을 사용한 반복 코드 제거

...

    private static void dfs(int y, int x, int depth) {
        answer = Math.max(answer, depth);

        for (int i = 0; i < 4; i++) {
            int _y = y + dy[i];
            int _x = x + dx[i];

            if (isValidCoord(_y, _x)&&!visited[getIdx(_y,_x)]){
                visited[getIdx(_y,_x)]=true;
                dfs(_y, _x, depth+1);
                visited[getIdx(_y,_x)]=false;
            }
        }
    }

    private static int getIdx(int y, int x){
        return grid[y][x]-65;
    }

...

BFS로 풀었고 메모리 초과가 발생했다. 질문 게시판을 찾아보고 구글링해보니 대부분 DFS로 풀었더라 그래서 DFS로 다시 풀었고 정답을 받을 수 있었다.

BFS는 안되고 DFS는 되는 이유

DFS로 풀어야 쓸데없는 경로로 가지 않는다고 한다. DFS는 다음번에 갈 수 있는 방향을 통제할 수 있는 반면에 BFS는 불가능하기 때문이다.

DFS는 다음 노드로의 이동이 가능하면 visited[idx]=true/visited[idx]=false를 해주는 백트래킹 기법을 사용할 수 있다. 반면 같은 방식으로 BFS에서 백트래킹을 구현하려고 하면 전역변수인 visited배열이나 Set을 이용해야 하는데, 알고리즘의 특성상 현재 노드를 처리할 때 방문처리를 해버리면 이후 Queue에서 DeQueue될 노드에서의 탐색에 제한이 생긴다. 자세히 말하면 DeQueue된 노드 기준으로 아직 방문하지 않은 노드임에도 방문 처리가 되어있기 때문에 방문이 불가능하며, 결과적으로 해당 노드를 방문해야 최적의 경로인 상황에서는 정답을 도출해낼 수 없는 것이다.

물론 내 최초 코드에서는 Status클래스를 생성해 각 인스턴스마다 방문 여부를 의미하는 Set을 필드로 갖게 했지만, 이 방법은 메모리 초과가 뜨는 관계로 검증해보지 못했다. 아마 같은 알파벳 조합을 history로 갖는 다수의 경로가 Queue에 머물기 때문이라고 생각된다. 이를 인지하고 같은 알파벳 조합이 두번 발생할 경우 continue하는 방법을 생각해봤지만 구현이 어려워 만들어 보지는 못했다.

결론은 DFS와 백트래킹을 이용해 푸는 것이 최적의 방법이라는 것이다.