[백준 JAVA] 1987번: 알파벳

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

 

처음 접했을때 R, C가 최대 20이라 맵의 사이즈는 400이고 DP로 풀 수 있을지 확인을 했다.

 

하지만 이전 경로값이 이후의 선택값에 영향을 주므로 DP는 힘들꺼라고 생각했고 DFS 또는 BFS를 활용하여 문제를 풀어야겠다고 생각했다.

 

이전의 경로를 방문배열로 처리하려 했기 때문에 큐에 이 방문배열을 전부 들고다녀야하는 BFS 보다는 DFS가 좀더 효율적일꺼같아서 DFS 로 문제를 풀이하였다.

 

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

public class Main {
    static int R, C, ans;
    static int[][] map;
    static int[] visited;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new int[R][C];
        visited = new int[26];
        ans = 0;
        for(int i = 0; i < R; i++){
            String str = br.readLine();
            for(int j = 0; j < C; j++){
                map[i][j] = str.charAt(j) - 'A';
            }
        }
        visited[map[0][0]] = 1;
        dfs(0, 0, 1);

        System.out.println(ans);
    }
    static void dfs(int r, int c, int depth){
        if(depth > ans) ans = depth;
        for(int d = 0; d < 4; d++){
            int nr = r + dr[d];
            int nc = c + dc[d];
            if(nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            int next = map[nr][nc];
            if(visited[next] == 1) continue;
            visited[next] = 1;
            dfs(nr, nc, depth + 1);
            visited[next] = 0;
        }
    }
}

 

시간복잡도를 정확히 하진 않고 바로 문제를 풀었는데 한번 계산해보겠다.

 

이 문제는 격자 크기가 최대 20×20이라 겉보기에는 최대 400칸을 모두 탐색해야 할 것처럼 보이지만 실제 탐색 깊이를 제한하는 조건은 “같은 알파벳을 두 번 밟을 수 없다”는 제약이다.

 

보드에 사용되는 문자는 대문자 알파벳 26개이므로 한 경로에서 DFS의 최대 깊이는 26을 넘을 수 없다. 각 단계에서 최대 4방향으로 이동할 수 있으므로 DFS 탐색의 이론적인 상한은 O(4^26)으로 잡을 수 있으며, 이는 매우 느슨한 상한이다.

 

상태를 (r, c, 사용한 알파벳 집합)으로 정의하면 가능한 알파벳 집합의 수는 2^26이고 좌표는 최대 R*C이므로 상태 수 기준으로는 O(R*C*2^26)의 상한을 갖는다. 다만 실제 탐색에서는 경계, 중복 알파벳, 이동 불가능한 경우로 인해 분기 수가 급격히 줄어들기 때문에 평균적인 실행 시간은 이보다 훨씬 작으며, 이러한 이유로 DFS 백트래킹 풀이가 제한 시간 내에 충분히 통과한다.