BOJ (Java) 1987번: 알파벳

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

---

풀이

dfs로 탐색하되, 현재 해당하는 위치 + 위치의 알파벳 방문 여부까지 확인하며 탐색한다.

이 때 알파벳 방문 여부는 비트마스킹을 사용했으나, visited 배열처럼 1차원 배열을 활용해도 가능하다. 

 

위가 비트마스킹, 아래가 1차원 배열 활용

---

Java 코드

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

public class Main {

    private static int R, C;
    private static int answer = 0;
    private static char[][] map;
    private static boolean[][] visited;
    private static int[][] mv = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

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

        // 표 정보 입력
        map = new char[R][C];
        visited = new boolean[R][C];
        for (int i = 0; i < R; i++) {
            String input = bf.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = input.charAt(j);
            }
        }

        // 지나온 알파벳 확인
        int alpha = 1 << 27;
        alpha |= 1 << (map[0][0] - 'A');
        visited[0][0] = true;
        findMax(0, 0, alpha, 1);
        System.out.println(answer);
    }

    // dfs 탐색, 지나온 알파벳 및 현재 이동횟수 카운트
    private static void findMax(int r, int c, int alpha, int moveCount) {
        boolean isMoved = false;
        for (int i = 0; i < 4; i++) {
            int nr = r + mv[i][0];
            int nc = c + mv[i][1];

            if (nr < 0 || nc < 0 || R <= nr || C <= nc
                    || visited[nr][nc] || (alpha & (1 << map[nr][nc] - 'A')) != 0) continue;

            visited[nr][nc] = true;
            findMax(nr, nc, alpha | 1 << (map[nr][nc] - 'A'), moveCount + 1);
            visited[nr][nc] = false;
            isMoved = true;
        }

        // 더 이상 움직일 수 없다면 최대 이동 횟수 갱신
        if (!isMoved) {
            answer = Math.max(answer, moveCount);
        }
    }
}