[그래프] 백준 5214

BFS를 사용해서 구현하되, 각 역간의 직선 연결로 할 시 java에서는 무조건 메모리 초과가 나게 되는 구조이다.

C, C++에서는 최대한 심플하게 인접 리스트를 활용하면 가능할 것으로 보인다.

해결 방법은, 각 역간을 연결하는 정보(하이퍼튜브)를 따로 리스트를 만들어 관리하고

각 역은 해당 하이퍼튜브를 바라보는 방향으로 인접 리스트를 구현하고

Queue를 이용해 최종 역을 찾아가는 과정을 수행하면 되는데,

최종 결과 출력 시 하이퍼튜브에 방문했던 수는 제외하고 각 역 간을 방문했을 때의 숫자만을 가지고 최종 결과를 만들어야 한다.

하이퍼튜브 방문 횟수를 빼기 위해 애초에 count를 계산할 때 역->하이퍼튜브 방문이면 +를 하지 않고, 하이퍼튜브->역 방문일 경우 +하는 방향으로 계산했다.

큐에 모든 역을 다 집어넣어도 최종 역에 도착하지 못했을 경우, -1을 출력하면 된다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        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<ArrayList<Integer>> dummyAddedList = new ArrayList<>();
 
        for (int i = 0; i <= N + M; i++) {
            dummyAddedList.add(new ArrayList<>());
        }
 
        for (int i = 0; i < M; i++) {
            int dummyLink = N + i + 1;
            st = new StringTokenizer(br.readLine(), " ");
 
            for (int j = 0; j < K; j++) {
                int tgt = Integer.parseInt(st.nextToken());
                dummyAddedList.get(tgt).add(dummyLink);
                dummyAddedList.get(dummyLink).add(tgt);
            }
 
        }
 
        boolean[] visited = new boolean[N + M + 1];
        Arrays.fill(visited, false);
        Queue<Integer> qu = new LinkedList<Integer>();
        qu.add(1);
        int[] cnt = new int[N + M + 1];
        cnt[1] = 1;
        visited[1] = true;
 
        while (!qu.isEmpty()) {
            int tmp = qu.poll();
            
            if(tmp==N){
                break;
            }
            ArrayList<Integer> set = dummyAddedList.get(tmp);
            for (int num : set) {
                if (!visited[num]) {
                    
                    qu.add(num);
                    visited[num] = true;
                    cnt[num] = tmp>N?cnt[tmp]+1:cnt[tmp];
                }
            }
        }
        System.out.println(visited[N]?cnt[N]:-1);
    }
}
 

각 원소 간 간선 정보가 많을 경우에는 연결 정보를 따로 관리하는 방식이 있다는 걸 배웠다.

 

무수한 오답의 향연들