[백준] 16947. 서울 지하철 2호선 (Java)

 

문제

16947번: 서울 지하철 2호선

 

 

알고리즘

그래프, 깊이우선탐색(DFS), 너비우선탐색(BFS)

 

 

풀이

DFS를 통해 사이클(순환선)을 찾아 표시하고,

BFS를 통해 사이클이 아닌 노드에서 사이클인 노드까지 최소 거리를 구해 문제를 해결하였다.

---

사이클 찾기 ( DFS )

모든 역은 연결되어있으므로 임의의 한 역에서 출발하여 DFS로 모든 간선을 탐색한다.

이때 이미 방문한 노드를 다시 방문한다면 사이클이 있는 것이므로 해당 노드까지 다시 되돌아가며 그 사이 역들을 모두 순환선으로 체크한다.

 

해당 노드까지 되돌아갔다면 사이클이 종료됐으므로 상태를 변경해야 그 노드를 호출한 이전 노드가 사이클로 체크되지 않는다.

예제 입력 5 그림 (가중치 제외)

 

위 그림에서 4 -> 8 -> 7 -> 6 -> 5 -> 4로 사이클을 발견했고

4부터 8까지 반환하며 모두 순환선으로 체크한다.

이때 다시 4로 돌아왔는데 사이클 종료로 상태를 바꾸지 않으면 4를 호출한 3, 1 번 역도 순환선으로 체크될 것이다.

 

---

역과 순환선 사이 거리 구하기 ( BFS )

 

모든 역을 탐색하며 해당 역이 순환선이라면 거리에 0을,

그렇지 않다면 BFS를 통해 순환선까지의 거리를 구해 삽입한다.

 

탐색을 마쳤다면 저장된 거리를 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, dist[];
	static boolean[] visited, cycle;
	static List<Integer>[] graph;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		visited = new boolean[N + 1];
		cycle = new boolean[N + 1];
		dist = new int[N + 1];
		graph = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			graph[i] = new ArrayList<Integer>();
		}

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());

			graph[A].add(B);
			graph[B].add(A);
		}

		dfs(1, 1);
		bfs();

		StringBuilder sb = new StringBuilder();
		for (int i = 1; i <= N; i++)
			sb.append(dist[i]).append(" ");
		System.out.println(sb);
	}

	private static void bfs() {
		label1: for (int i = 1; i <= N; i++) {
			if (cycle[i]) continue;

			Queue<Integer[]> queue = new LinkedList<>();
			visited = new boolean[N+1];
			
			queue.add(new Integer[] { i, 0 });
			visited[i] = true;

			while (!queue.isEmpty()) {
				Integer[] cur = queue.poll();

				for (int next : graph[cur[0]]) {
					if(visited[next]) continue;
					visited[next] = true;
					
					if (cycle[next]) {
						dist[i] = cur[1] + 1;
						continue label1;
					}
					queue.add(new Integer[] { next, cur[1] + 1 });
				}
			}
		}

	}

	private static boolean dfs(int before, int cur) {
		if (visited[cur]) {
			return cycle[cur] = true;
		}

		for (int next : graph[cur]) {
			if (next == before) continue;
			visited[cur] = true;

			if (dfs(cur, next)) {
				if (cycle[cur]) return false;
				return cycle[cur] = true;
			}
		}

		return cycle[cur];
	}
}