[JAVA] 백준 (골드4) 1987번 알파벳

링크

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

---

문제 설명

정답률 28.207%
세로 $R$칸, 가로 $C$칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 ($1$행 $1$열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

---

입력 예제

2 4
CAAB
ADCB

---

출력 예제

3

---

풀이

일반적인 그래프 탐색 문제이다. DFS를 이용하여 최대 이동 거리를 구한다.

각 칸마다 알파벳이 적혀있는데, 이 알파벳을 List로 저장하여 방문을 처리한다면 반복적인 중복 체크 및 추가/삭제를 하면서 시간 복잡도가 비효율적이므로 boolean 배열로 체크한다.

boolean[] visited = new boolean[26];

또한 보드를 char 배열로 생성하여 알파벳의 ASCII 값을 활용해 방문 여부를 확인한다.

//시작지점 방문 처리
visited[board[0][0] - 'A'] = true;

이제 DFS로 모든 방향을 탐색하면서 최대한 갈 수 있는 만큼 재귀를 호출한다.

전체 코드

//백준
public class Main {

    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static char[][] board;
    static int R, C, max = 0;
    static boolean[] visited = new boolean[26];  //알파벳 방문 체크

    public static void main(String[] args) throws Exception {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] split = br.readLine().split(" ");
        R = Integer.parseInt(split[0]);
        C = Integer.parseInt(split[1]);

        board = new char[R][C];
        for (int i = 0; i < R; i++) {
            board[i] = br.readLine().toCharArray();
        }

        //시작지점 방문 처리
        visited[board[0][0] - 'A'] = true;
        dfs(0, 0, 1);

        System.out.println(max);
    }

    static void dfs(int r, int c, int count) {
        max = Math.max(max, count);

        for (int i = 0; i < 4; i++) {
            int nextR = r + dr[i];
            int nextC = c + dc[i];

            if (nextR < 0 || nextR >= R || nextC < 0 || nextC >= C) {
                continue;
            }

            char nextChar = board[nextR][nextC];
            if (!visited[nextChar - 'A']) {
                visited[nextChar - 'A'] = true;
                dfs(nextR, nextC, count + 1);
                visited[nextChar - 'A'] = false;
            }
        }
    }
}