[BOJ] 1987. 알파벳 (🥇, 백트래킹)

🔗

풀이

좌측 상단인 좌표 (0, 0)에서 시작하여 모든 보드를 탐색하며 최대 몇 칸 지날 수 있는지 확인하는 문제이다. 전체 보드의 크기가 최대 400이기 때문에 완전 탐색으로 진행하여도 시간 초과는 발생하지 않을 수 있다.

특정 시점에서 가능한 모든 방향에 대해 확인해야 한다. 여기서 가능한 경우는 현재까지 지나온 경로 중에 앞으로 방문할 알파벳이 없는 경우이다. 즉 같은 알파벳을 두 번 방문하는 것은 불가능하다. 이런 탐색의 경우는 항상 방문처리를 통해서 계속 같은 자리를 방문하지 않을 수 있도록 하는 것이 중요한데 이 문제에서는 이미 같은 알파벳을 다시 방문하는 것은 불가능하다는 조건을 걸어서 방문처리까지 한꺼번에 처리할 수 있도록 제시해주고 있다.

그래서 깊이 우선 탐색을 통해 가능한 모든 경로에 대해 탐색하면서 매번 탐색의 최대 길이를 업데이트한다. 이후 현재 위치에서 방문 가능한 모든 위치에 대해서 현재까지 방문한 적 없는 알파벳의 경우에만 방문하는 것으로 한다. 이렇게 처리하게 되면 이미 방문한 위치에 대해 방문하지 않을 수 있고, 문제의 조건에서처럼 같은 알파벳을 두 번 방문하는 일도 없을 수 있다.

import java.util.*;
import java.io.*;

public class Main {
    static char[][] board;
    static int answer = 0;
    static boolean[] alpha = new boolean[26];
    static int R;
    static int C;
    static final int GAP = 'A';
    static int[][] direction = new int[][] {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();
        
        board = new char[R][C];
        for (int i = 0; i < R; i++) {
            board[i] = sc.next().toCharArray();
        }
        
        alpha[board[0][0] - GAP] = true;
        
        dfs(0, 0, 1);
        System.out.println(answer);
    }

    private static void dfs(int x, int y, int count) {
        answer = Math.max(answer, count);

        int nx; 
        int ny;
        char a;
        for (int i = 0; i < 4; i++) {
            nx = x + direction[i][0];
            ny = y + direction[i][1];
            
            if (nx < 0 || ny < 0 || nx >= R || ny >= C || alpha[board[nx][ny] - GAP]) continue;
            a = board[nx][ny];
            alpha[a - GAP] = true;
            dfs(nx, ny, count+1);
            alpha[a - GAP] = false;
        }
    }
}