1987번: 알파벳

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 주어집니다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸(1행 1열)에는 말이 놓여 있습니다. 말은 상하좌우로 인접한 네 칸 중 한 칸으로 이동할 수 있는데, 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 다른 알파벳이 적힌 칸으로만 이동할 수 있습니다. 좌측 상단에서 시작하여 말이 최대로 지날 수 있는 칸의 수를 구하는 문제입니다.

• 입력: 첫째 줄에 R과 C가 주어집니다. (1 ≤ R, C ≤ 20) 둘째 줄부터 R개의 줄에 걸쳐 보드에 적혀 있는 알파벳이 주어집니다.
• 출력: 말이 지날 수 있는 최대의 칸 수를 출력합니다.

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

풀이: 알파벳 중복 체크와 백트래킹

경로 상의 알파벳이 중복되지 않도록 상하좌우를 탐색하며 최장 경로를 찾아야 하므로 DFS와 백트래킹을 사용해야 합니다.

1. 알파벳 사용 여부 체크 (alpha 배열): 지금까지 밟은 알파벳을 기록하기 위해 크기가 26인 boolean 배열을 사용합니다. 알파벳 대문자가 주어지므로, 현재 문자 - 'A'를 인덱스로 삼으면 0부터 25까지의 인덱스로 변환하여 O(1)의 속도로 중복 여부를 확인할 수 있습니다.
2. DFS 탐색 및 백트래킹:
   • 매 탐색(DFS 호출)마다 지나온 칸의 수(d)와 기존 최댓값(ans)을 비교하여 갱신합니다.
   • 4방향을 탐색하며 맵의 범위를 벗어나지 않고, 아직 밟지 않은 알파벳인 경우에만 이동합니다.
   • 다음 칸으로 이동하기 전 알파벳을 사용 처리(alpha[...] = true)하고 dfs를 재귀 호출한 뒤, 탐색을 마치고 돌아왔을 때는 다른 경로 탐색을 위해 사용 처리를 해제(alpha[...] = false)해 주는 백트래킹 로직을 적용합니다.

코드

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

public class Main {
    static int r, c, ans;
    static char[][] a;
  
    static boolean[] alpha = new boolean[26];
    
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

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

       StringTokenizer st = new StringTokenizer(br.readLine());
       r = Integer.parseInt(st.nextToken());
       c = Integer.parseInt(st.nextToken());
       
       a = new char[r][c];
       for (int i = 0; i < r; i++) {
          a[i] = br.readLine().toCharArray();
       }

       // 시작 위치(0, 0)의 알파벳 방문 처리 후 탐색 시작 (초기 이동 칸 수 1)
       alpha[a[0][0] - 'A'] = true;
       dfs(0, 0, 1);

       bw.write(ans + "");

       bw.flush();
       bw.close();
       br.close();
    }

    static void dfs(int y, int x, int d) {
       // 탐색할 때마다 최대 칸 수 갱신
       ans = Math.max(ans, d);
       
       for (int i = 0; i < 4; i++) {
          int ny = y + dy[i];
          int nx = x + dx[i];
          
          // 보드 범위를 벗어나면 무시
          if (ny < 0 || nx < 0 || ny >= r || nx >= c)
             continue;
             
          // 이미 지나온 경로에서 사용한 알파벳이라면 무시 (재방문도 함께 방지됨)
          if (alpha[a[ny][nx] - 'A'])
             continue;
             
          // 방문 처리
          alpha[a[ny][nx] - 'A'] = true;
          
          // 다음 칸으로 깊이 탐색 진행
          dfs(ny, nx, d + 1);
          
          // 다른 경로를 찾기 위해 상태 복구 (백트래킹)
          alpha[a[ny][nx] - 'A'] = false;
       }
    }
}

알고리즘 분류

그래프 탐색, 깊이 우선 탐색 (DFS), 백트래킹 (Backtracking)