[백준] 5214 환승 -JAVA

5214번: 환승 (acmicpc.net)

5214번: 환승

 

누구나 쉽게 BFS를 떠올릴수 있지만 메모리와 시간 초과를 피하기 위해 새로운 발상이 필요했던 문제.

풀이

알고리즘 파악

BFS

 

일반적인 BFS 방식으로는 메모리 초과나 시간 초과가 날 수 밖에 없다. 

하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M의 범위는 1≤K,M≤1,000이다. 하이퍼튜브 하나당 정점끼리 K*K 개의 간선이 연결되므로 그래프의 총 간선의 개수는 최악의 경우 O(M*K*K)=1,000,000,000개이다. 

 

이런 비효율성을 극복기위해 그래프의 간선을 줄이는 방법이 있다.

 

각 역들을 역들끼리 연결시키지 말고, 역이 속한 하이퍼튜브를 간선으로 삼는 것이다. 

 

구현

 

1.  간선의 기준을 각 역이 속한 하이퍼 튜브를 삼는다. 만약 1번 역이 1,2,3 번 하이퍼튜브에 속해있으면 해당 하이퍼튜브를 역의 간선으로 삼는다. 

 

2.  역을 qeueu에 넣고 bfs를 돌린다. 

 

3.  해당역이 속한 하이퍼튜브(간선)의 다른역들을 전부 방문한다. 그리고 해당 하이퍼튜브와 역들은 전부 방문처리 한다. 방문하지 않은 역은 queue에 넣는다. 

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	static int n,k,m;
	static int answer=1;
	static ArrayList<Integer>[] graph; //그래프 
	static boolean[] tubes_visit,visit; //튜브와 역의 visit
	static int[][] tubes;
	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());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
	    
        graph = new ArrayList[n+1];
        visit = new boolean[n+1];
	    tubes_visit = new boolean[m];
	    tubes = new int[m][k];
	    for(int i=1; i<=n; i++) graph[i] = new ArrayList<>();
	    
        for(int i=0; i<m; i++)
        {
        	 st =new StringTokenizer(br.readLine());
        	 for(int j=0; j<k; j++) 
        	 {
        		 int num =  Integer.parseInt(st.nextToken());
        		 tubes[i][j] = num;
        		 graph[num].add(i); 
        	 }
        }
        
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        visit[1] = true;
        if(n>1) bfs(q); //n이 1인 경우는 예외로 함
	    bw.write(Integer.toString(answer));
        bw.flush();
        bw.close();
        br.close();
	}
	
	static void bfs(Queue<Integer> q)
	{
		answer++;
		Queue<Integer> nq = new LinkedList<>();
	
		while(!q.isEmpty())
		{
		   int num = q.poll();
		   ArrayList<Integer> list = graph[num]; //역이 속한 튜브들
		   
		   for(int tube_idx:list)
		   {
			  if(!tubes_visit[tube_idx]) //튜브 방문
			  {
				  tubes_visit[tube_idx] = true;
				  int[] tube = tubes[tube_idx];
				  for(int station:tube)
				  {
					  if(station == n) return;
					  if(!visit[station]) //역 방문
					  {
						  visit[station] = true;
						  nq.offer(station);
					  }
				  }
			  }
		   }	
		}

		if(!nq.isEmpty()) bfs(nq);
		else answer = -1;
	}
}