백준 : 5214

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

5214번: 환승

 

처음에는 모든간선을 TreeSet 을 이용해서 중복을 없애주고 연결해주었다.

하지만 최악의경의 1000^3 만큼 간선이 생길수가 있다. 이렇게하면 메모리초과가 발생한다.

따라서 반대로 역을 하나로 묶은것을 Node로 만들고 간선을 하나의 역으로 만들면 M은 최대 1000 이기때문에 메모리초과가 발생하지 않는다.

package day0229;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class B5214 {
    static int N, K, M;
    static ArrayList<Integer> ver[];
    static int Node[][];
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        ver = new ArrayList[N + 1];
        Node = new int[M + 1][K + 1];
 
        for (int n = 1; n <= N; n++) {
            ver[n] = new ArrayList<Integer>();
        }
 
        for (int m = 1; m <= M; m++) {
            st = new StringTokenizer(br.readLine());
            for (int k = 0; k < K; k++) {
                Node[m][k] = Integer.parseInt(st.nextToken());
                ver[Node[m][k]].add(m);
            }
        }
 
        boolean visit[] = new boolean[M + 1];
 
        Queue<Integer> q = new LinkedList<Integer>();
        if (N != 1) {
 
            for (int s = 0; s < ver[1].size(); s++) {
                visit[ver[1].get(s)] = true;
                q.add(ver[1].get(s));
            }
 
            int Answer = -1;
            int time = 2;
 
            while (!q.isEmpty()) {
 
                int size = q.size();
                for (int s = 0; s < size; s++) {
                    int tmp = q.poll();
                    
                    //집합안에 N이 잇으면
                    for(int k=0;k<K;k++) {
                        if(Node[tmp][k] ==N) {
                            Answer = time;
                            break;
                        }else {
                            for(int i=0;i<ver[Node[tmp][k]].size();i++) {
                                if(visit[ver[Node[tmp][k]].get(i)]) continue;
                                visit[ver[Node[tmp][k]].get(i)]=true;
                                q.add(ver[Node[tmp][k]].get(i));
                            }
                        }
                    }
                    if(Answer!=-1)break;
                    
                    
                }
 
                if (Answer != -1) {
                    break;
                }
                time++;
            }
 
            System.out.println(Answer);
        }else {
            System.out.println(1);
        }
 
    }
}