아이디어

• BFS나 DFS를 사용하여 탐색하면 될 것 같다. 여기선 BFS를 사용해보겠다.
• 이때, 도착한 점이 같더라도 이전에 갔던 경로가 다르면 다른 경우로 취급해야 한다.
  • 따라서 방문 배열을 전역적으로 사용하는 게 아닌, 각 도착점마다 가지고 있어야 한다.
  • 다행히 $1 \le R \times C \le 25$이므로, 비트마스킹을 이용하면 충분히 담을 수 있을 것으로 보인다.
• depth $K-1$까지 BFS를 진행한 뒤, 마지막으로 큐에 남은 노드의 개수가 갈 수 있는 모든 경로의 수이다.

코드

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

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer tk = null;

    static int R, C, K;
    static boolean[][] map;  // 'T'인지 여부

    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    static Queue<Node> q = new ArrayDeque<>();
    static int ans;

    public static void main(String[] args) throws Exception {
        tk = new StringTokenizer(rd.readLine());
        R = Integer.parseInt(tk.nextToken());
        C = Integer.parseInt(tk.nextToken());
        K = Integer.parseInt(tk.nextToken());

        map = new boolean[R][C];
        for (int y=0; y<R; y++) {
            char[] s = rd.readLine().toCharArray();
            for (int x=0; x<C; x++) {
                map[y][x] = s[x] == 'T';
            }
        }

        // bfs until depth K-1
        q.add(new Node(R-1, 0, 0x0));

        for (int depth=1; depth<=K-1; depth++) {
            int size = q.size();
            for (int i=0; i<size; i++) {
                Node node = q.remove();
                int y = node.y;
                int x = node.x;
                int flags = node.flags;

                for (int d=0; d<4; d++) {
                    int ny = y + dy[d];
                    int nx = x + dx[d];
                    if (ny < 0 || ny >= R || nx < 0 || nx >= C) continue;
                    if (map[ny][nx]) continue;
                    if (isVisited(flags, ny, nx)) continue;

                    q.add(new Node(ny, nx, flags | (1 << toFlagIdx(y, x))));
                }
            }
        }

        // depth K일 때 좌표가 y=0, x=C-1인 노드 개수 세기
        while (!q.isEmpty()) {
            Node node = q.poll();
            if (node.y == 0 && node.x == C-1) {
                ans++;
            }
        }

        System.out.println(ans);
    }

    static class Node {
        int y, x, flags;
        Node(int y, int x, int flags) {
            this.y = y;
            this.x = x;
            this.flags = flags;
        }
    }

    static int toFlagIdx(int y, int x) {
        return y * C + x;
    }

    static boolean isVisited(int flags, int y, int x) {
        return ((flags >> toFlagIdx(y, x)) & 1) == 1;
    }
}

메모리 및 시간

• 메모리: 19580 KB
• 시간: 196 ms

리뷰

• 경로가 다르면 다른 경우로 취급한다는 것을 어떻게 풀어내야 하나 고민했던 문제
• 중간에 toFlagIdx()를 y*C+x가 아닌 y*R+x로 잘못 구현하는 오류가 있었다.
• 알고리즘 분류에 BFS나 비트마스크가 없는데, DFS 만을 사용해서 풀 수 있나?
  • 찾아보니, DFS로 노드를 탐색한 후 visit 처리를 되돌려 놓으면 되는 것이었다.
  • BFS는 $R$과 $C$가 작아서 가능했던 편법이었던 모양이다.