문제

풀이 과정

요약

DFS 를 활용한 문제. 아 분명 이렇게 하면 시간초과 날 거 같은데 했는데 안 난 문제.

상세

1. 입력값을 받고 시작값에서 DFS() 를 호출한다.

2. 해당 문제는, 탐색을 하면서 만약 임의의 방향으로 현재 갈 수 있는 최대거리 좌표 $G$ 까지 도달했다면 그 이전 호출로 돌아가 $G$ 좌표를 다시 방문처리를 해제하는 것으로 최적화 할 수 있다. (여기는 이 방향의 $G$ 까진 도달했으니 다른 방향의 $G$ 로 가보자! 약간 이런느낌)

3. 예외로, 방문처리가 총 26이므로 비트마스킹을 통해 방문처리를 하였다. (확실히 메모리도 적게들고, 계산 시간도 좀 더 빠르다)

정답

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

public class Main {
    static int R, C;
    static int[][] map;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, -1, 0, 1};
    static int ans;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        R = Integer.parseInt(stk.nextToken());
        C = Integer.parseInt(stk.nextToken());

        map = new int[R][C];
        for (int i = 0; i < R; i++) {
            char[] temp = br.readLine().toCharArray();
            for (int j = 0; j < C; j++) {
                map[i][j] = temp[j] - 'A';
            }
        }
        DFS(0, 0, 1 << map[0][0], 1);
        System.out.println(ans);
    }

    public static void DFS(int r, int c, int bit, int dist) {
        if (dist > ans) ans = dist;

        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr < 0 || nc < 0 || nr >= R || nc >= C || (bit & 1 << map[nr][nc]) > 0) continue;
            DFS(nr, nc, bit | 1 << map[nr][nc], dist + 1);
        }
    }
}