[백준 1987] 알파벳 (JAVA)

문제

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

풀이

DFS를 이용해 해결할 수 있습니다. 어떤 알파벳을 거쳐 갔는지 boolean 배열을 이용할 수도 있지만, 알파벳은 총 26자이기 때문에 비트마스킹을 이용해 해결하면 더 빠르게 문제를 해결할 수 있습니다.

코드

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

public class Main {

    static int R, C, visit, ans = 0;
    static int[][] map;
    static int[][] check;
    static int[][] dt = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new int[R][C];
        check = new int[R][C];

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

        visit = 1 << map[0][0];
        dfs(0, 0, 1);

        System.out.println(ans);
        br.close();
    }

    static void dfs(int x, int y, int cnt) {

        if (check[x][y] == visit) return;
        check[x][y] = visit;

        for (int d = 0; d < 4; d++) {
            int dx = x + dt[d][0];
            int dy = y + dt[d][1];
            if (dx >= 0 && dx < R && dy >= 0 && dy < C && ((visit & (1 << map[dx][dy])) == 0)) {
                visit |= 1 << map[dx][dy];
                dfs(dx, dy, cnt + 1);
                visit &= ~(1 << map[dx][dy]);
            }
        }
        ans = Math.max(ans, cnt);
    }
}