[백준] 1987. 알파벳

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

1987번: 알파벳

• 처음에는 set을 사용해서 매 경우마다 set을 clone하고 새로운 알파벳을 넣어주는 식으로 풀었다. 그런데 시간초과가 났다. 아무래도 매번 컬렉션을 복제하는 것이 시간이 많이 소요되는 거 같다.
• 따라서 set이 아니라, 알파벳을 담는 일차원 배열을 두면 된다. 즉, visited[] 배열을 두어서 A를 방문했으면 visited[0] = true로 값을 넣어주는 식으로 하면 된다. 
• 주의할 점으로는, 재귀를 나온 후에 visited 배열을 초기화해주어야 한다. 재귀로 인해 깊이 우선 탐색이기 때문에 하나의 깊이를 탐색하고 탐색이 끝난 후에 visited 배열을 초기화해주면 다음 탐색에 영향을 주지 않는다. 즉, 앞서 set을 clone하는 식으로 복제할 필요가 없는 것이다.
• 시간 복잡도는 하나의 노드가 4방향으로 이동할 수 있기 때문에 노드 갯수가 N이라고 할 때, 4^N이다(위로 가거나, 아래로 가거나, 왼쪽으로 가거나, 오른쪽으로 가거나). 그러나 최대 이동할 수 있는 노드의 갯수는 알파벳 수만큼이기 때문에 4^26이 된다. 

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

// 시간 복잡도: O(4^26)
public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int r;
    static int c;
    static int[][] map;
    static boolean[] visited;
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int answer = 0;

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        map = new int[r][c];
        visited = new boolean[26];

        for (int i = 0; i < r; i++) {
            String input = br.readLine();
            for (int j = 0; j < c; j++) {
                map[i][j] = input.charAt(j) - 'A';
            }
        }

        // 0,0부터 dfs
        dfs(0, 0, 1);

        System.out.println(answer);
    }

    private static void dfs(int y, int x, int count) {

        visited[map[y][x]] = true; // 알파벳 방문 처리
        answer = Math.max(answer, count);

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

            if (nx < 0 || nx >= c || ny < 0 || ny >= r) {
                continue;
            }

            // map[ny][nx]의 알파벳을 이미 방문하지 않았을 때만
            if (!visited[map[ny][nx]]) {
                dfs(ny, nx, count + 1);
                visited[map[ny][nx]] = false; // 재귀 나온 후에는 초기화
            }
        }
    }
}