백준 1987번 알파벳 (Java, DFS)

문제 설명

https://www.acmicpc.net/problem/1987

2차원 보드 위에서 알파벳이 적혀 있습니다.
(0, 0)에서 시작해서 상하좌우로 이동하며 같은 알파벳을 한 번만 밟을 수 있다면, 최대 몇 칸을 이동할 수 있을까요?

 

DFS + 백트래킹을 이용하여 중복되지 않은 알파벳 경로의 최대 길이를 찾는 문제입니다.

---

입력

• 첫 줄: 세로 R(1 ≤ R ≤ 20), 가로 C(1 ≤ C ≤ 20)
• 그 다음 R줄: 각 줄에 C개의 알파벳 대문자

---

출력

• 말이 지나갈 수 있는 최대 칸 수 (중복된 알파벳은 지나갈 수 없음)

---

예제 입력

2 4
CAAB
ADCB

예제 출력

 

3

---

코드 구현 (Java)

import java.util.*;

public class Main {
    static int R, C;
    static char[][] board;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static Set<Character> set = new HashSet<>();
    static int answer = 0;

    public void DFS(int depth, int x, int y) {
        answer = Math.max(answer, depth);

        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 && !set.contains(board[nx][ny])) {
                set.add(board[nx][ny]);
                DFS(depth + 1, nx, ny);
                set.remove(board[nx][ny]); // 백트래킹
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();
        sc.nextLine(); // 개행 문자 제거

        board = new char[R][C];
        for (int i = 0; i < R; i++) {
            String s = sc.nextLine();
            for (int j = 0; j < C; j++) {
                board[i][j] = s.charAt(j);
            }
        }

        set.add(board[0][0]); // 시작 알파벳 등록
        T.DFS(1, 0, 0); // depth는 1부터 시작
        System.out.print(answer);
        sc.close();
    }
}

---

코드 설명

1. DFS 함수 정의 및 최대 길이 갱신

public void DFS(int depth, int x, int y) {
    answer = Math.max(answer, depth);

 

• 현재까지 이동한 칸 수(depth)를 기준으로 answer를 갱신합니다.
• depth는 현재까지 밟은 알파벳 수입니다.

2. 상하좌우 4방향 탐색

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

 

 

 

• 상, 하, 좌, 우로 이동하기 위한 좌표 계산입니다.
• dx, dy 배열은 이동 방향을 나타냅니다.

3. 방문 여부 검사 및 재귀 호출

if (nx >= 0 && nx < R && ny >= 0 && ny < C && !set.contains(board[nx][ny])) {
    set.add(board[nx][ny]);
    DFS(depth + 1, nx, ny);
    set.remove(board[nx][ny]); // 백트래킹
}

 

• 이동 가능한 범위 안에 있고, 이미 방문한 알파벳이 아니라면 이동
• 방문 후 DFS 재귀 호출
• 탐색이 끝나면 set.remove()로 상태 복원 → 백트래킹 핵심

4. DFS 시작

set.add(board[0][0]);
T.DFS(1, 0, 0);

 

 

• 시작 위치의 알파벳을 먼저 방문 처리
• depth = 1부터 시작해야 (0,0) 칸이 포함된 경로로 정확히 계산됨

 

 

---

시간 복잡도

• 보드의 최대 크기: 20 x 20 = 400칸
• 중복되지 않은 알파벳: 최대 26개
• 즉, 알파벳 경로 최대 길이는 26
• 각 칸에서 최대 4방향 이동 → 최악의 경우 4^26 가지 탐색
• 하지만 Set으로 중복 알파벳을 막으므로 실제 탐색은 훨씬 적음
  → 백트래킹을 통한 가지치기 + 알파벳 제한 덕분에 충분히 시간 내 해결 가능