백준 16166 서울의 지하철 자바(java)

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

16166번: 서울의 지하철

 

풀이 방법

BFS 를 사용하여 구현하였다.

문제의 메모리 제한이 128MB = 2^27 인데 역 번호는 2^32 - 1 이하의 정수로 무작위 입력되므로 BFS 구현 시 visited 배열을 역 번호 크기만큼 선언해줄 수 없다. 이를 해결할 방법을 생각해야 한다.

역은 (최대 호선의 개수 x 최대 역의 개수) = 10 x 10 하여 최대 100개의 다른 번호가 주어질 수 있다. 따라서 입력 받은 역 번호의 값을 0~99번 중 하나로 매핑하여 저장해주면 메모리 초과없이 최대 100 크기의 배열을 선언하여 구현할 수 있다. 

• ArrayList 배열 stations를 생성하여 역 번호에 해당하는 호선들을 저장한다.
  • ex) 2번 역이 3, 4호선에 해당된다면 stations[2] = {3, 4}
• ArrayList 배열 lines를 생성하여 각 호선 별로 포함하는 역 번호를 저장한다.
  • ex) 3호선이 1, 2, 3번 역을 지난다면 lines[3] = {1, 2, 3}
• Map 을 생성하여 Key: 입력받은 원래의 역 번호, value: 0~99번 중 바꾼 역 번호를 저장한다.
• visited[호선][역 번호] 2차원 배열을 선언하여 방문 체크한다.
• 0번 역에서 출발이므로 큐에 0번 역과 0번 역에 해당하는 모든 호선을 삽입한다.
• 큐에서 꺼낸 역이 도착역이면 반복문을 탈출하여 환승 횟수를 출력한다.
• 도착역이 아니면 현재 호선이 포함하는 방문하지 않은 모든 역을 환승 없이 큐에 삽입하고 방문 체크한다.
• 그 다음, 현재 역에서 다른 호선으로 환승하여(현재 환승 횟수+1) 큐에 삽입하고 방문 체크한다.
• 도착역에 도착할 때까지 또는 큐가 빌 때까지 반복한다.

 

코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer>[] stations = new ArrayList[100]; // 역 번호에 해당하는 호선 저장
        ArrayList<Integer>[] lines = new ArrayList[N+1]; // 각 호선 별로 포함하는 역 번호 저장
        Map<Integer, Integer> map = new HashMap<>(); // 입력받은 역 번호를 0~99번으로 치환하여 저장

        for(int i=0; i<100; i++) {
            stations[i] = new ArrayList<>();
        }

        int num = 0; // 원래의 역 번호 -> 0~99번으로 바꾸어줌
        for(int i=1; i<=N; i++) {
            String[] line = br.readLine().split(" ");
            int K = Integer.parseInt(line[0]);
            lines[i] = new ArrayList<>();
            for(int j=1; j<=K; j++) {
                int station = Integer.parseInt(line[j]);
                if(!map.containsKey(station)) {
                    map.put(station, num);
                    stations[num].add(i);
                    lines[i].add(num);
                    num++;
                } else {
                    stations[map.get(station)].add(i);
                    lines[i].add(map.get(station));
                }
            }
        }
        int M = Integer.parseInt(br.readLine());

        Queue<int[]> q = new LinkedList<>();
        boolean[][] visited = new boolean[N+1][100];
        for(Integer line : stations[map.get(0)]) {
            q.add(new int[]{0, map.get(0), line}); // 환승횟수, 역 번호, 호선
            visited[line][map.get(0)] = true;
        }
        boolean isArrived = false;
        int answer = 0;
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            int cnt = cur[0];
            int curStation = cur[1];
            int curLine = cur[2];
            // 도착역에 도착했으면
            if(curStation == map.get(M)) {
                isArrived = true;
                answer = cnt;
                break;
            }
            // 같은 라인에 있는 역은 환승 안하고 큐에 넣기
            for(Integer nextStation : lines[curLine]) {
                if(!visited[curLine][nextStation]) {
                    visited[curLine][nextStation] = true;
                    q.add(new int[]{cnt, nextStation, curLine});
                }
            }
            // 현재 역의 다른 호선으로 환승하여 큐에 넣기
            for(Integer nextLine : stations[curStation]) {
                if(!visited[nextLine][curStation]){
                    visited[nextLine][curStation] = true;
                    q.add(new int[]{cnt+1, curStation, nextLine});
                }
            }
        }
        if(!isArrived) {
            System.out.println(-1);
        } else {
            System.out.println(answer);
        }
    }
}