백준 5214 환승 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/5214

풀이는 다음과 같다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 하이퍼루프도 노드로 보자: x번째 하이퍼루프를 N+x index에 할당
        // 그래서 visited와 distance, 그리고 그래프 A 배열의 크기도 그에 맞게 설정
        ArrayList<Integer>[] A = new ArrayList[N+1+M];
        for (int i = 0 ; i <= N+M ; i++) {
            A[i] = new ArrayList<>();
        }
        boolean[] visited = new boolean[N+1+M];
        int[] distance = new int[N+1+M];

        for (int i = 0; i < M; i++) {
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            for (int j = 0; j < K; j++) {
                int num = Integer.parseInt(st1.nextToken());
                A[num].add(N+i+1); //해당 역에 하이퍼루프 추가
                A[N+i+1].add(num); //해당 하이퍼루프에 역 추가
            }
        }

        //위와 같이 초깃값 세팅하면,
        //1번 역의 하이퍼루프로 가서 해당 하이퍼루프의 역들을 돌고
        //해당 하이퍼루프의 역에서 또 하이퍼루프로 가고
        //이렇게 된다.
        //즉, 따라서 1에서 N을 간다고 하면, 어떠한 경로이든 하이퍼루프 노드, 실제 노드를 번갈아가면서 간다.
        //그래서 거리는 하이퍼루프를 돌때는 추가되어야하지 않지만 +1 되니까, /2 를 해주어야 한다.

        // BFS
        Queue<Integer> q = new ArrayDeque<Integer>();
        q.add(1);
        visited[1] = true;
        distance[1] = 1;
        while (!q.isEmpty()) {
            int now = q.poll();
            for (int next: A[now]) {
                if (visited[next]) continue;
                visited[next] = true;
                distance[next] = distance[now]+1;
                q.add(next);
            }
        }

        if(visited[N]) {
            bw.write(String.valueOf(distance[N]/2 + 1));
        }
        else {
            bw.write(String.valueOf(-1));
        }

        bw.flush();
        bw.close();
    }


}

이전의

이 문제와 비슷하다.
역과 호선(하이퍼루프) 가 있고, 최소거리를 구해야 한다.
https://velog.io/@dlsrjsdl6505/%EB%B0%B1%EC%A4%80-16166-%EC%84%9C%EC%9A%B8%EC%9D%98-%EC%A7%80%ED%95%98%EC%B2%A0-%EC%9E%90%EB%B0%94

하지만,
이전 문제는 역<=1000, 호선<=11
이 문제는 역<=100000, 호선<=1000 이었기 때문에
이전 문제와 똑같은 방식으로 풀었을때는 메모리 이슈가 있어서 해결되지 못했다.
(아래 코드)

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

public class Main {
    //호선 == 하이퍼튜브 (true)
    static ArrayList<Integer>[] A = new ArrayList[1001]; //한 호선 역들
    static ArrayList<Integer>[] B = new ArrayList[100001]; //한 역 호선들
    static boolean[][] visited = new boolean[1001][100001]; //호선, 역 순서 방문배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000)
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st1.nextToken());
        int K = Integer.parseInt(st1.nextToken());
        int M = Integer.parseInt(st1.nextToken());
        
        for(int i = 1 ; i <= N ; i++) {
            B[i] = new ArrayList<>();
        }
        
        for(int i = 1 ; i <= M ; i++) {
            A[i] = new ArrayList<>();
        }
        
        
        //다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫자는 그 하이퍼튜브가 서로 연결하는 역의 번호이다.
        for(int i = 1 ; i <= M ; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            for(int j = 1 ; j <= K ; j++) {
                int num = Integer.parseInt(st2.nextToken());
                A[i].add(num);
                B[num].add(i);
            }
        }
        
        //초깃값

        bw.write(String.valueOf(BFS(N)));
        bw.flush();
        bw.close();
        
    }
    //BFS
    static int BFS(int end) {
        int answer = -1;
        PriorityQueue<Station> q = new PriorityQueue<>();
        
        for(int line : B[1]) {
            q.add(new Station(1, line, 1));
        }
        
        while(!q.isEmpty()) {
            Station curStation = q.poll();
            int curNum = curStation.num;
            int curLine = curStation.line;
            int curCnt = curStation.cnt;
            
            if(visited[curLine][curNum]) continue;
            visited[curLine][curNum] = true;
            
            if(curNum == end) return curCnt;
            
            for(int nextLine : B[curNum]) {
                if(!visited[nextLine][curNum]) {
                    q.add(new Station(curNum, nextLine, curCnt)); //같은 역 호선 옮기는건 역 이동한거 아니잖아
                }
            }
            
            for(int nextNum : A[curLine]) {
                if(!visited[curLine][nextNum]) {
                    q.add(new Station(nextNum, curLine, curCnt+1));
                }
            }
            
        }
        
        return answer;
    }
    
    
    
    //역 클래스 (역숫자, 호선숫자, 몇개타고왔는지)
    static class Station implements Comparable<Station> {
        int num;
        int line;
        int cnt;

        public Station(int num, int line, int cnt) {
            this.num = num;
            this.line = line;
            this.cnt =  cnt;
        }

        public int compareTo(Station e) {
            if(this.cnt > e.cnt) return 1;
            else return -1;
        }
    }

}

역을 하나의 노드로 잡았는데, 그럼
그래프를 인접 행렬로 저장: 역이 최대 10만개, N^2 == 100억 -> 애초에 memory에서 불가능

그래서 문제를 맞추기위해서
다르게 코드를 짠 부분은
이전 코드는 역이 가진 호선, 호선이 가진 역 그래프를 두개를 만들었고
호선마다 역에 대한 방문 체크를 따로 해주었다면,
(1호선 1역과 2호선 1역은 방문 배열따로)

이 문제는 역 변호와 호선까지 그래프를 하나로 통일시키고 (크기 N+M+1)
방문 배열 또한 역과 호선으로 하나로 만들었다. (크기 N+M+1)
아무래도 이전문제 링크를 통해 이해하고 오면 훨씬 이해가 빠를것 같다.

ps.
나는 골드 5인 이전 문제가 더 어려운것같다..