[ 백준 ] 1987 알파벳

Link | 백준 1987번 문제 : 알파벳

📌 About

1행 1열 부터 시작으로 상하좌우를 DFS으로 탐색하면 된다.

이 때 백트래킹을 적용하여 방금 찾은 문자의 탐색 여부를 변경한다.

📌 Solution

Step 0. Initialize

주어진 문자 보드를 읽으면서 board 배열에 저장한다.

이때 board 배열의 크기는 탐색의 편의를 위해 R+2 * C+2 로 한다.

추가로 알파벳의 탐색 여부를 저장하는 boolean 배열을 초기화한다.

1행 1열도 탐색에 포함되기 때문에 1행 1열의 문자는 true로 한다.

private char[][] board;
private int max = 0;

private final boolean[] alphabets = new boolean[26];
private final int[][] moves = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

private void init() throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    int row = Integer.parseInt(tokenizer.nextToken());
    int col = Integer.parseInt(tokenizer.nextToken());
    board = new char[row + 2][col + 2];
    for (int r = 1; r <= row; r++) 
        System.arraycopy(reader.readLine().toCharArray(), 0, board[r], 1, col);
    alphabets[board[1][1] - 65] = true;
}

Step 1. 백트래킹 탐색

탐색한 문자에서의 탐색 문자 개수를 max에 계속해서 업데이트 한다.

업데이트 후에는 상하좌우를 탐색한다.

만약 탐색하고자 하는 위치가 board 영역 밖이거나 이미 탐색한 알파벳이면 탐색하지 않는다.

private void search(int row, int col, int count) {
    max = Math.max(max, count);
    for (int[] move : moves) {
        if (board[row + move[0]][col + move[1]] != '\u0000' && !alphabets[board[row + move[0]][col + move[1]] - 65]) {
            alphabets[board[row + move[0]][col + move[1]] - 65] = true;
            search(row + move[0], col + move[1], count + 1);
            alphabets[board[row + move[0]][col + move[1]] - 65] = false;
        }
    }
}

📌 Code

GitHub Repository

private char[][] board;
private int max = 0;

private final boolean[] alphabets = new boolean[26];
private final int[][] moves = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

public void solve() throws IOException {
    init();
    search(1, 1, 1);
    result.append(max);
}

private void init() throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    int row = Integer.parseInt(tokenizer.nextToken());
    int col = Integer.parseInt(tokenizer.nextToken());
    board = new char[row + 2][col + 2];
    for (int r = 1; r <= row; r++)
        System.arraycopy(reader.readLine().toCharArray(), 0, board[r], 1, col);
    alphabets[board[1][1] - 65] = true;
}

private void search(int row, int col, int count) {
    max = Math.max(max, count);
    for (int[] move : moves) {
        if (board[row + move[0]][col + move[1]] != '\u0000' && !alphabets[board[row + move[0]][col + move[1]] - 65]) {
            alphabets[board[row + move[0]][col + move[1]] - 65] = true;
            search(row + move[0], col + move[1], count + 1);
            alphabets[board[row + move[0]][col + move[1]] - 65] = false;
        }
    }
}