[JAVA] 백준 5214번 【G2.환승】

문제

5214번: 환승

 

풀이

1️⃣ bfs와 인접리스트를 이용한 풀이

💡 참고한 Idea

역의 수 N이 최대 100000 이고 하이퍼 튜브와 하이퍼 튜브가 연결하는 역의 개수 K 와 M이 최대 1000 이라서

일반적인 그래프를 푸는 방식으로 노드를 연결하면 시간 복잡도가 말도안되게 커져서 고민을 많이 했다.

계속 메모리 초과를 어떻게 해결해야할지 고민하다가 다른 사람의 아이디어를 참고하였다.

하이퍼 튜브를 일종의 역으로서 생각을 하고 노드로서 추가하는 것이다.

그러면 공간복잡도를 많이 줄일 수 있었다.



예를 들어 역 1번과 

역 1, 2, 3, 4 을 연결하는 하이퍼 튜브 1 이 있다고 가정할 때

기존에는 역 (1,2) (1,3) (1,4) (2,3) (2,4) (3,4) 을 연결했지만

하이퍼 튜브 1 을 역 5로 가정하고 연결하면 

(1,5) (2,5) (3,5) (4,5) 만 연결해주면 된다. 

역의 개수가 늘어날수록 기존 방식에 비해 연결하는 횟수는 크게 감소하게될 것이다.


그리고 bfs를 통해 탐색을 하는데, 하이퍼 튜브에 해당하는 역을 지나갈때에는 카운팅을 해주지 않는 방식으로 거쳐간 역의 개수를 구할 수 있다.

 

 

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]), K = Integer.parseInt(input[1]), M = Integer.parseInt(input[2]);

        List<List<Integer>> nodes = new ArrayList<>();
        
        // 리스트의 N-1 번까지는 역, N 부터 M-1 까지는 하이퍼튜브(가짜 역)
        for (int i = 0; i < N + M; i++) {
            nodes.add(new ArrayList<>());
        }

		// 역과 하이퍼 튜브 연결
        for (int i = 0; i < M; i++) {
            input = br.readLine().split(" ");
            int hyperTube = N + i;
            for (int j = 0; j < K; j++) {
                int connectedStation = Integer.parseInt(input[j]) - 1;
                nodes.get(hyperTube).add(connectedStation);
                nodes.get(connectedStation).add(hyperTube);
            }
        }


        Queue<Integer> q = new LinkedList<>();
        int[] checked = new int[N + M];
        q.offer(0);
        
        // 체크 배열에 거쳐간 횟수를 기록
        checked[0] = 1;

        while (!q.isEmpty()) {
            int num = q.poll();
            if (num == N - 1) {
                System.out.println(checked[num]);
                System.exit(0);
                break;
            }

            List<Integer> connects = nodes.get(num);

            for (int connect : connects) {
            	// 아직 거쳐간 역이 아닌 경우만
                if (checked[connect] == 0) {
                	// 역이 하이퍼 튜브가 아닌 경우 거쳐간 횟수 + 1
                    if (connect < N) {
                        checked[connect] = checked[num] + 1;
                        q.offer(connect);
                    // 다음 역이 가짜 역(하이퍼 튜브) 인 경우 횟수 증가를 하지 않음    
                    } else {
                        checked[connect] = checked[num];
                        q.offer(connect);
                    }
                }
            }
        }
        System.out.println(-1);
    }
}

 

결과

 

처음에는 역을 거쳐간 횟수도 int[] 배열로 큐에 집어넣는 방식을 했었는데, 이렇게 하면 메모리초과가 발생해서 횟수는 배열로서 따로 체크를 하는 방식을 적용하였다.