백준 환승(5214)

환승

1. 힌트

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

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

3) 입력으로 주어지는 M×KM \times K

2. 접근

1) 그래프

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

그래프의 정점의 정의를 (i(i번째 역))으로 정의해봅시다. 만약 어떤 정점이 (1)(1)이라면 현재 몇 번째 하이퍼루프에 타고있는 걸까요?
알 수가 없습니다. 따라서 정점의 정의에 하이퍼루프 번호를 추가해서 (i(i번째 하이퍼 루프, jj번째 역))으로 정의해봅시다. 이러면 그래프의 상태 공간의 크기가 O(M×N)O(M \times N)

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

3. 구현

1) 0-1 BFS

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

2) 하이퍼루프간 간선

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

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

dist[there][0]=1dist[there][0] = -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);
    }

}

좋은 웹페이지 즐겨찾기