[백준 *Java] - 알파벳(1987)

알파벳

1987번: 알파벳

 

문제

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

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

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

입력

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

출력

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

---

👇접근 방식

이 문제는 BackTracking 방식을 이용하여, 문제 구현을 해야한다고 생각을 먼저 들었습니다.
dfs 구현 도중에 방문처리를 해주면서, 탐색을 해주어야하는데, 처음에는 boolean을 2차원으로 설계를 했었습니다.
그러면서 해당 알파벳 값을 가지고 동일한 알파벳이 있다면? 방문을 하였으니 빠지는 형태로 가려고 했지만, 매번 지나왔는 지 알파벳을 또 알파벳 배열에서 탐색을 해줘야하나? 생각을 하다가 애초에 알파벳 자체가 한정되어있는 수로 아스키코드 변환을 하면 될 거 같다는 생각을 하게 됐습니다.
그러면, 따로 방문했던 알파벳을 또 탐색을해서 찾을 필요 없이. 알파벳 불린 배열을 하나가지고 true / false 로 방문처리 관리를 해주면 된다고 생각을 했습니다. 
아래 그림은 테스트케이스 2번을 가지고 로직설계를 할 때 그렸던 그림입니다.
그림1은 입력받은 board 판을 row와 col로 구분 지어서 사방면 탐색을 하기 위해 보기 편하게 그린 그림이고.
그림2는 깊이우선 탐색으로 가지치기를 하면서 탐색하는 과정을 그려놓습니다.

(그림1). 테스트케이스 2번

 

(그림2). 테스트케이스 2번. 알파벳 배열(visited)로 방문처리를 하며 탐색

아래는 성공한 코드입니다.

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

public class Boj_알파벳 {
    private static int row, column;
    private static char[][] board;
    private static boolean[] visited = new boolean[26]; // 알파벳 수만큼
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};
    private static final int fourDirection = 4;
    private static int max = Integer.MIN_VALUE;

    public static void dfs(int r, int c, int count) {
        max = Math.max(max, count);
        // recur
        for (int i = 0; i < fourDirection; i++) {
            int movedRow = r + dx[i];
            int movedColumn = c + dy[i];
            if (movedRow < 0 || movedColumn < 0 || movedRow >= row || movedColumn >= column) continue;
            int moveHorse = board[movedRow][movedColumn] - 65;
            if (!visited[moveHorse]) {
                visited[moveHorse] = true;
                dfs(movedRow, movedColumn, count + 1);
                // backTracking
                visited[moveHorse] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // R과 C 값 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        row = Integer.parseInt(st.nextToken());
        column = Integer.parseInt(st.nextToken());
        board = new char[row][column];

        for (int i = 0; i < row; i++) {
            char[] line = br.readLine().toCharArray();
            for (int j = 0; j < column; j++) {
                board[i][j] = line[j];
            }
        }
        visited[board[0][0] - 65] = true;
        dfs(0, 0, 1);
        System.out.println(max);
    }
}