[Baekjoon Online Judge] 1987번: 알파벳

1987번: 알파벳

요구사항

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

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

 - 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성한다.

입력

 - 첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1 ≤ R,C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳들이 빈칸 없이 주어진다.

출력

 - 첫째 줄에 말이 지날 수 있는 최대의 칸 수를 출력한다.

---

DFS와 BFS를 모두 사용하여 문제를 해결해보려 하였다. 하지만 BFS로 백트래킹 구현에 어려움이 있기 때문에 DFS로 해결하였다.

 

입력받은 알파벳을 board 이차 배열에 저장한다. 그 후 DFS 방문하며 최대 칸 수를 구한다. 이때 방문한 알파벳은 visited 배열에 표시해둔다.

 

DFS로 재귀호출을 마무리하면 재방문을 위해서 방문 기록을 지워간다.

 

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

public class Baekjoon1987 {

    static int r, c, max;
    static char[][] board;
    static boolean[] visited;
    static int[] xMove = {-1, 1, 0, 0};
    static int[] yMove = {0, 0, -1, 1};

    private static void dfs(int x, int y, int d) {

        visited[board[x][y] - 'A'] = true;
        for (int i = 0; i < 4; i++) {
            int currentX = x + xMove[i];
            int currentY = y + yMove[i];

            if (isLocation(currentX, currentY)) {
                System.out.println("x: " + x + " | y: " + y + " | d: " + d); // 디버깅
                dfs(currentX, currentY, d + 1);
            }
        }
        visited[board[x][y] - 'A'] = false;
        max = Math.max(max, d);
    }

    private static boolean isLocation(int x, int y) {
        if (x > 0 && y > 0 && x <= r && y <= c && !visited[board[x][y] - 'A']) return true;
        return false;
    }

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

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        String[] input = bufferedReader.readLine().split(" ");

        // 1 <= r, c <= 20
        r = Integer.parseInt(input[0]);
        c = Integer.parseInt(input[1]);

        board = new char[r + 1][c + 1];
        visited = new boolean[26]; // 방문한 알파벳

        for (int i = 1; i < board.length; i++) {
            String[] row = bufferedReader.readLine().split("");
            for (int j = 1; j < board[i].length; j++) {
                board[i][j] = row[j - 1].charAt(0);
            }
        }

        dfs(1, 1, 1);
        System.out.println(max);

        bufferedReader.close();
    }
}