[Baekjoon] 1987번: 알파벳 - Java

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

1987번: 알파벳

문제 설명

DFS 문제를 살짝 응용한 문제이다.

풀이 방법

핵심이 되는 DFS 함수는 다음과 같다.

private static void dfs(int r, int c, int count) {
    if (isDuplicated[board[r][c]]) {
        MAX = Math.max(MAX, count);
        return;
    } else {
        isDuplicated[board[r][c]] = true;

        for (int i = 0; i < 4; i++) {
            int nextX = r + dx[i];
            int nextY = c + dy[i];

            if (nextX >= 0 && nextY >= 0 && nextX < R && nextY < C)
                dfs(nextX, nextY, count + 1);
        }

        isDuplicated[board[r][c]] = false;
    }
}

이미 나왔던 알파벳이라면 이때까지의 카운트와 최댓값을 비교하여 갱신하고 함수를 종료한다.

 

처음 나온 알파벳이라면 알파벳 체크를 하고 범위 내의 상하좌우를 다시 탐색해 나간다. 이때 기존 카운트에 1을 더해서 넘겨준다. 이때 버그를 예방하기 위해 증감 연산자가 아닌 더하기 연산을 하여 넘겨준다.

 

상하좌우 모두 갈 곳이 없다면 돌아가면서 체크했던 알파벳을 취소한다. 이렇게 취소 작업을 하지 않으면 다른 DFS 경로에서 탐색할 때 문제가 발생한다. 다른 경로에서는 해당 알파벳을 체크한 적이 없는데 먼저 실행된 경로에서 체크해 버렸기 때문이다.

 

전체 코드는 다음과 같다.

package baekjoon.dfs_bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ1987 {
    static int R;
    static int C;
    static int MAX = Integer.MIN_VALUE;
    static int[][] board;
    static boolean[] isDuplicated = new boolean[26];
    static final int[] dx = {0, 1, 0, -1};
    static final int[] dy = {1, 0, -1, 0};

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

            board = new int[R][C];

            for (int i = 0; i < R; i++) {
                String input = br.readLine();
                for (int j = 0; j < C; j++) {
                    board[i][j] = input.charAt(j) - 'A';
                }
            }

            dfs(0, 0, 0);

            System.out.println(MAX);
        }
    }

    private static void dfs(int r, int c, int count) {
        if (isDuplicated[board[r][c]]) {
            MAX = Math.max(MAX, count);
            return;
        } else {
            isDuplicated[board[r][c]] = true;

            for (int i = 0; i < 4; i++) {
                int nextX = r + dx[i];
                int nextY = c + dy[i];

                if (nextX >= 0 && nextY >= 0 && nextX < R && nextY < C)
                    dfs(nextX, nextY, count + 1);
            }

            isDuplicated[board[r][c]] = false;
        }
    }
}