백준 환승(5214)

환승

1. 힌트

1) 하이퍼튜브를 타고 이동하는 경우 간선의 가중치는 $0$이고 하이퍼튜브에서 내려서 다른 하이퍼튜브를 이용할 때의 가중치를 $1$로 정의할 수 있습니다.

2) 그래프를 구성하는 것이 핵심입니다. 하이퍼 튜브로 연결된 정점끼리 $O(K^2)$개의 간선을 모두 연결하면 간선의 개수가 너무 많아집니다. 하이퍼튜브로 직접적으로 이어진 정점을 가중치가 $0$인 간선으로 이어줍니다.

3) 입력으로 주어지는 $M \times K$배열을 곧이 곧대로 그래프라고 생각하고 $(i$번째 하이퍼루프, $j$번째 역$)$으로 정점을 정의하고, 좌우로 인접한 역끼리는 가중치가 $0$인 간선으로 정의하고, 다른 하이퍼루프를 이동하는 경우는 가중치가 $1$이 되도록 구현할 수 있습니다.

2. 접근

1) 그래프

그래프를 구성하고 BFS를 이용하면 최단 거리를 구할 수 있습니다. 이 문제에서 거리는 중간 과정에서 방문한 역의 개수입니다. 그런데 하이퍼루프를 이용하면 역을 방문하지 않고도 이동할 수 있기 때문에 그래프의 구성을 조금 달리 할 필요가 있습니다.

그래프의 정점의 정의를 $(i$번째 역$)$으로 정의해봅시다. 만약 어떤 정점이 $(1)$이라면 현재 몇 번째 하이퍼루프에 타고있는 걸까요?
알 수가 없습니다. 따라서 정점의 정의에 하이퍼루프 번호를 추가해서 $(i$번째 하이퍼 루프, $j$번째 역$)$으로 정의해봅시다. 이러면 그래프의 상태 공간의 크기가 $O(M \times N)$으로 너무 커집니다.
따라서 그래프를 입력으로 주어지는 $M \times K$배열처럼 정의합시다. $(i$번째 하이퍼 루프, $i$번째 하이퍼루프의 $j$번째 역$)$

이번엔 그래프의 간선을 정의해야합니다. 간선의 가중치는 하이퍼루프에서 내리는 경우 $1$이고 하이퍼루프를 타고 이동하는 경우는 $0$입니다. 하이퍼루프 내의 모든 정점 간에 가중치 $0$짜리 간선을 이어줄 필요 없이 바로 왼쪽과 바로 오른쪽 정점간에 간선을 이어주기만 해도 됩니다.
하이퍼루프에서 내리는 경우는 모든 하이퍼루프간에 가중치 $1$짜리 간선을 이어줄 수 있습니다.

3. 구현

1) 0-1 BFS

간선에 가중치가 있는 그래프에서 최단 거리는 Dijkstra로 구하는 것이 일반적이지만, 우리가 구성한 그래프에서는 가중치가 $0$혹은 $1$이기때문에 Deque를 사용하여 0-1 BFS를 해줄 수 있습니다.

2) 하이퍼루프간 간선

$adj[i]$는 $i$번째 하이퍼루프와 연결된 다른 하이퍼루프를 저장합니다. 중복될 필요가 없으므로 Set으로 저장합니다. 가장 처음 $1$번 역에서는 어떤 하이퍼루프든지 탈 수 있으므로 모두 Deque에 넣어줍니다.

3) 다른 하이퍼루프로 환승하는 경우

$dist[there][0] = -1$인지 확인합니다. 하필이면 $0$번째 역을 확인하는 이유는 하이퍼루프끼리의 간선의 가중치는 $0$이기 때문에 $i$번째 하이퍼루프를 한번이라도 방문했다면 $dist[i][j] (0 \le j < K)$는 모두 $-1$이 아니기 때문입니다.

public class Main {

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder bw = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        ArrayList<Set<Integer>> adj = new ArrayList<>(N);
        for (int i = 0; i <= N; i++) adj.add(new HashSet<>());
        int[][] S = new int[M][K];
        Deque<int[]> q = new LinkedList<>();
        int[][] dist = new int[M][K];
        for (int i = 0; i < M; i++) Arrays.fill(dist[i], -1);
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < K; j++) {
                S[i][j] = Integer.parseInt(st.nextToken());
                adj.get(S[i][j]).add(i);
                if (S[i][j] == 1) {
                    q.offer(new int[] { i, j });
                    dist[i][j] = 0;
                }
            }
        }
        while (!q.isEmpty()) {
            int[] p = q.poll();
            int y = p[0]; int x = p[1];
            // 하이퍼루프를 따라 양 옆으로 이동하는 경우
            for (int d = 0; d < 2; d++) {
                int nx = x + dx[d];
                if (0 <= nx && nx < K && dist[y][nx] == -1) {
                    q.offerFirst(new int[] { y, nx });
                    dist[y][nx] = dist[y][x];
                }
            }
            // 다른 하이퍼루프로 환승하는 경우
            for (int there : adj.get(S[y][x])) if (dist[there][0] == -1) {
                q.offerLast(new int[] { there, 0 });
                dist[there][0] = dist[y][x] + 1;
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < K; j++) {
                if (S[i][j] == N) {
                    if (dist[i][j] != -1) {
                        min = Math.min(min, dist[i][j]);
                    }
                }
            }
        }
        if (min == Integer.MAX_VALUE) min = -1;
        else if (N != 1) min += 2;
        else min = 1;
        bw.append(min).append("\n");
        System.out.print(bw);
    }

}