[백준] 16947 서울 지하철 2호선 - JAVA

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

16947번: 서울 지하철 2호선

 

 

알고리즘

• DFS + BFS
• 순환선에 포함되는 역을 찾는다. DFS
• (무방향)그래프 내에서 순환을 찾기 위한 방법 : DFS/ Union-find 
  💡처음에 유니온 파인드로 시도했으나, 사이클이 있다는 것은 확인되지만 사이클에 포함되는 노드가 제대로 찾아지지 않아서 DFS로 ! 
• 순환선에 포함되지 않은 역은 순환선까지의 최소값을 구하기 위해 BFS로 접근 

---

 

🌟 그래프 내에서 순환 찾기 

• isCycle[] : 사이클에 포함된 역인지 확인하기 위한 boolean 형 배열 

 

순환 조건 

1. 시작점 == 도착점 

2. 시작점과 도착점 사이에 2개 이상의 역이 존재해야 한다. (ex) 1-3-1 : 순환 아님) 

 

2번 조건을 판별하기 위해 현재 탐색 중인 node 에 대해 직전 노드(prev)와 다음노드(next)가 같은지 확인하였다. 만약 prev==next  라면 1-3-1 과 같은 경우이므로 순환이 아니다. 

 

• 현재 노드에 연결되어 있는 다음 노드가 사이클에 포함되어 있지 않다면, DFS 재귀 계속해서 진행 
• 다음 노드가 사이클에 포함되어 있다면, prev != next (1-3-1 방지) && next == start 일 경우에만 순환 O 

 

만약 순환이 아닐 경우, 다음 시작노드로 부터의 탐색을 위해 isCycle 값을 다시 false 로 바꾼 뒤 false 반환 

static boolean dfs(int prev, int node, int start) {
		isCycle[node] = true; 
		
		for(int next: list.get(node)) {
			if(!isCycle[next]) {
				if(dfs(node, next, start)) return true; 
			}
			else {
				//이미 방문했던 곳인데, 시작점을 만났을 때, 바로 이전 정점이 아닐때 
				//next==prev 이면, 1-3-1 과 같이 바로 돌아온 경우 (순환 x ) 
				if(next != prev && next ==start) return true; 
			}
		}
		isCycle[node]=false; //사이클 못났으면 다시 false 로 바꿔주기 
		return false; 
	}

 

---

구현 과정

• list : 역 간 연결 정보를 그래프로 구현하기 위한 인접 리스트 
• isCycle : 해당 역이 순환선에 포함되어 있다면 true 
• dfs : 순환선을 찾기 위한 dfs 탐색 
• bfs : 순환선 까지의 최단거리를 찾기 위한 bfs 탐색 

 

1. 역 간 연결 정보를 입력받아 list 에 저장한다. 

 

2. DFS 탐색을 통해 순환선을 찾는다. 

 

3. 순환선에 포함된 역이라면 0을 출력하고, 그렇지 않다면 BFS 탐색을 통해 순환선까지의 최단 거리를  구한다. 

 

---

소스 코드

import java.util.*;
import java.io.*;
	
public class Main {
	static ArrayList<ArrayList<Integer>> list = new ArrayList<>(); 
	static int N; 
	static boolean isCycle[]; 
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st;
		
		N= Integer.parseInt(br.readLine());//역의 갯수 		
		for(int i=0; i<=N; i++) {
			list.add(new ArrayList<Integer>()); 
		}
		
		for(int i=0; i<N; i++) {
			st= new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken()); 

			list.get(a).add(b);
			list.get(b).add(a);
		}
		
		isCycle = new boolean[N+1]; 
		for(int i= 1; i<=N; i++) {
			//1~N 역을 출발점으로 하여 사이클이 만들어 지는지 확인 
			if(dfs(i,i,i)) break; //사이클 만나면 종료 
		}


		StringBuilder sb= new StringBuilder(); 
		for(int i=1; i<=N; i++) {
			//순환선에 포함되어 있는 역이라면 0 출력
			if(isCycle[i]) sb.append(0); 
			else sb.append(bfs(i)); 
			sb.append(" "); 
		
		}
		
		System.out.println(sb);
		
	}//end of main 
	
	static boolean dfs(int prev, int node, int start) {
		isCycle[node] = true; 
		
		for(int next: list.get(node)) {
			if(!isCycle[next]) {
				if(dfs(node, next, start)) return true; 
			}
			else {
				//이미 방문했던 곳인데, 시작점을 만났을 때, 바로 이전 정점이 아닐때 
				//next==prev 이면, 1-3-1 과 같이 바로 돌아온 경우 (순환 x ) 
				if(next != prev && next ==start) return true; 
			}
		}
		isCycle[node]=false; //사이클 못났으면 다시 false 로 바꿔주기 
		return false; 
	}
	
	static class Node implements Comparable<Node>{
		int node; 
		int dis; 
		public Node(int node, int dis) {
			this.node= node;
			this.dis= dis; 
		}
		@Override
		public int compareTo(Node o) {
			return this.dis -o.dis; 
		}
		
	}
	//노드에서 순환까지의 최소 거리 찾기 
	static int bfs(int node) {
		boolean visited[] = new boolean[N+1]; 
		PriorityQueue<Node> que =new PriorityQueue<>(); 
		que.add(new Node(node, 0)); 
		visited[node] = true; 
		
		while(!que.isEmpty()) {
			Node now_node = que.poll();
			int now= now_node.node;
			int dis= now_node.dis;
			
			//순환 만남 
			if(isCycle[now]) return dis; 
			
			for(int i=0; i<list.get(now).size(); i++) {
				int next= list.get(now).get(i); 
				
				if(visited[next]) continue; 
				
				visited[next] = true; 
				que.add(new Node(next, dis+1)); 
			}
		}
		return -1; 
	}
}//end of class