문제

해설

이 문제는 그래프에서 여러 루트를 탐색하면서 최적의 루트를 찾아야 하는 문제이기 때문에 전형적인 DFS - 백트래킹 문제이다.

좌측 상단의 1행 1열에서 시작하여 DFS를 이용하여 보드를 탐색해나가는데 방문한 알파벳을 기록한다.
방문 알파벳을 기록하는 방식은 알파벳의 개수인 26만큼의 인덱스 개수를 갖고 있는 boolean 배열인 visited를 만들고 해당 위치의 보드에 있는 알파벳에서 'A'를 빼서 visited 배열의 0번 인덱스인 A를 기준으로 몇 번째 알파벳인지를 추출하여 그 숫자의 visited 배열의 인덱스를 방문한 알파벳이라는 표시를 위해 True로 전환하였다.

또한 탐색을 진행하면서 해당 위치를 몇 번째만에 갈 수 있는지를 나타내는 수치인 depth를 dfs()의 파라미터로 함께 넘겨주고 만약 조건(보드의 범위 안인 동시에 아직 방문하지 않은 알파벳)을 만족하면 기존 depth에 +1을 하여 재귀 호출하였다.
만약 파라미터로 넘어온 depth의 수치가 정답(최대한 지날 수 있는 칸 수)을 나타내는 기존 maxDepth(최대 깊이)보다 더 크다면 갱신해줘야 한다.

이 때 가장 중요한 게 해당 칸에서 더 이상 조건을 만족하는 루트가 없어 각 재귀 함수가 종료되면서

visited[board[x][y] - 'A'] = true;

백트래킹 방식을 통해 해당 알파벳의 방문 기록을 해제해줘야 한다.

왜냐하면 방문 기록을 해제하지 않으면 더 이상 조건을 만족하는 루트가 없어 함수가 종료되어 이전 칸으로 거슬러 올라가서(더 최적의 루트를 찾기 위해 이전 루트는 없었던 셈 치고) 이전 칸에서 다른 루트를 탐색해보려고 시도할 때에 한 번 방문한 알파벳을 다시 탐색할 수 없기 때문에 특정 경로를 탐색한 후 다른 경로를 시도할 수 없으므로 maxDepth 값이 제대로 갱신되지 않아 최적의 해를 찾기 못하는 문제점이 발생한다.

백트래킹(Backtracking)은 문제 해결을 위한 알고리즘 설계 기법 중 하나로, 재귀적 탐색을 통해 문제의 해를 찾는 방식이다.

주어진 문제에서 가능한 모든 해를 탐색하면서 조건을 만족하지 않는 경우에는 더 이상 진행하지 않고 이전 단계로 돌아가서 다른 가능한 경로를 탐색하는 방식이다. 이러한 방식을 "되돌리기"(backtracking)라고도 한다.

1. 백트래킹의 핵심 아이디어

탐색 트리를 구성하여 가능한 해를 모두 탐색한다.
각 단계에서 유효하지 않은 선택을 발견하면, 해당 경로를 더 이상 진행하지 않고 되돌아가(backtrack) 다른 경로를 시도한다.
(백트래킹은 깊이 우선 탐색(DFS)의 변형으로 볼 수 있다.)

2. 백트래킹의 일반적인 과정

1. 현재 상태에서 선택: 가능한 선택 중 하나를 선택하고, 그 선택을 다음 단계로 이어서 진행한다.

2. 유효성 검사: 현재 선택이 조건을 만족하는지 확인합니다. 조건을 만족하면 계속 진행하고, 만족하지 않으면 되돌아가서 다른 선택을 한다.

3. 되돌리기(backtrack): 선택이 잘못된 경로였다고 판단되면, 이전 상태로 돌아가서 다른 선택을 시도한다.

4. 해를 찾으면 종료: 해가 발견되면 결과를 반환하고 종료한다.

정답 코드

Java

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

public class Main {
    static int R, C, maxDepth;
    static char[][] board;
    static boolean[] visited = new boolean[26]; // A-Z 방문 여부 체크
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

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

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        board = new char[R][C];

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

        maxDepth = 0;
        dfs(0, 0, 1);
        sb.append(maxDepth);
        System.out.println(sb);
    }

    private static void dfs(int x, int y, int depth) {
        maxDepth = Math.max(maxDepth, depth); // 현재까지의 최대 깊이 갱신
        visited[board[x][y] - 'A'] = true; // 현재 위치의 알파벳 방문 체크

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < R && ny >= 0 && ny < C) {
                if (!visited[board[nx][ny] - 'A']) { // 새로운 알파벳이라면
                    dfs(nx, ny, depth + 1); // 다음 칸은 기존 깊이보다 + 1
                }
            }
        }

        visited[board[x][y] - 'A'] = false; // 백트래킹 (방문 해제)
    }
}

Python

import sys
input = sys.stdin.readline

R, C = map(int, input().split())

board = [list(sys.stdin.readline().strip()) for _ in range(R)]
visited = [False] * 26
max_depth = 0
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


def dfs(x, y, depth):
    global max_depth
    max_depth = max(max_depth, depth)
    visited[ord(board[x][y]) - ord('A')] = True

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < R and 0 <= ny < C:
            if not visited[ord(board[nx][ny]) - ord('A')]:
                dfs(nx, ny, depth + 1)

    visited[ord(board[x][y]) - ord('A')] = False


dfs(0, 0, 1)
print(max_depth)