[Java] 백준 16947번 : 서울 지하철 2호선*

1. 문제

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

16947번: 서울 지하철 2호선

 

 

 

2. 풀이 과정

1. 사이클 찾기(DFS)

모든 경로를 돌다가 아래 두 조건을 만족하면, 사이클이므로 return true를 하고 사이클 요소에 true표시

1) 방금 전에 방문한 노드 != 다음에 방문할 노드

2) 이미 방문한 노드

dfs로 돌아가다가 출발점을 마주치면 return false로 사이클 요소 true표시를 종료한다.

 

2. 사이클에서부터 거리 찾기(BFS)

사이클인 요소 중에서 연결된 path가 3개 이상일 경우, 사이클 외에 다른 경로가 있으므로 BFS로 탐색하여 거리를 업데이트 해준다.

 

import java.io.*;
import java.util.*;

public class Main {
	static int N, result[];
	static ArrayList<Integer> edges[];
	static boolean visited[], cycle[];
	
	public static boolean findCycle(int before, int n) {
		for(int next : edges[n]) {
			if(next==before) {continue;}
			if(visited[next]) {
				cycle[next] = true;
				return true;
			}
			visited[next] = true;
			if(findCycle(n, next)) {
				if(cycle[next]) {return false;}
				cycle[next] = true;
				return true;
			}
		}
		return false;
	}
	
	public static void bfs(int su) {
		Queue<Integer> q = new LinkedList<>();
		q.add(su);
		visited[su] = true;
		int distance = 1;
		
		while(!q.isEmpty()) {
			for(int i=0, size=q.size(); i<size; i++) {
				int now = q.poll();
				for(int next : edges[now]) {
					if(cycle[next]) {continue;}//사이클이면
					if(result[next]!=0) {continue;}
					result[next] = distance;
					q.add(next);
				}	
			}
			distance++;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		edges = new ArrayList[N+1];
		result = new int[N+1];
		visited = new boolean[N+1];
		cycle = new boolean[N+1];

		for(int i=1; i<=N; i++) {
			edges[i] = new ArrayList<>();
		}
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
			edges[n1].add(n2);
			edges[n2].add(n1);
		}
		//사이클 찾기
		visited = new boolean[N+1];
		visited[1] = true;
		findCycle(1, 1);
			
		//사이클에서 거리 계산
		for(int i=1; i<=N; i++) {
			if(cycle[i] && edges[i].size() > 2) {
				bfs(i);
			}
		}
		
		//result
		for(int i=1; i<=N; i++) {
			System.out.print(result[i]+" ");
		}
	}

}

 

결과