[백준] code.plus(그래프 알고리즘,JAVA)16947번, 서울 지하철 2호

문제 링크

16947번: 서울 지하철 2호선

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

그래프 알고리즘이란?

각 정점과 연결하는 선분의 정보를 가지고 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) .... 등을 이용하여 정점에서 다른 정점으로 가는 최소값, 최대값 등의 문제에서 출력하라는 결과를 구하는 알고리즘입니다.

이 문제에 핵심은

1. 역이 N개 있으면 역과 역을 연결하는 구간도 N개가 존재한다.

2. 구간은 양방향 간선으로 본다.

3. 순환선은 무조건 1개, 지선은 2개가 존재

4. 모든 역에서 순환선에 속하는 역의 최소 거리를 결과로 출력합니다.

 

주어진 역들의 정보를 가지고 DFS(깊이 우선 탐색)을 진행하여 순환선에 속해있는 점들을 찾았습니다.

 

각 역을 시작으로 BFS(너비 우선 탐색)을 진행하여 순환선에 속해있는 가장 가까운 역의 거리를 구해서 출력하였습니다.

 

사이클이 존재한다는 것은 방문했던 역을 다시 방문할 때 사이클이 형성됩니다.

DFS탐색으로 사이클이 발견되었을 때 이전으로 돌아가며 사이클에 속한 역을 배열에 저장합니다.

 

예제입력1

1 -> 3

4 -> 3

4 -> 2

1 -> 2

 

DFS 탐색시

1 -> 3 -> 4 -> 2 -> 1 사이클 형성

 

1, 2, 3, 4는 순환선에 포함되는 역으로 저장

 

각 역에서 순환선에 포함된 역에 최소 거리를 구할 때

 

순환선에 포함되면 0 출력

포함되지 않으면 BFS 탐색으로 가장 가까운 순환선에 포함된 역의 거리 출력

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 역에 대한 정보를 저장하였습니다.
• DFS탐색으로 순환선 내에 포함되는 역을 구하는 dfs함수를 실행하였습니다.
• 각 역에서 순환선 내 가장 가까운 역과의 거리를 구하는 bfs함수를 실행하였습니다.
• 각 역에서 최소 거리를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• dfs함수는 DFS로 탐색하여 순환선 내 포함되는 역을 찾는 함수입니다.
• bfs함수는 BFS로 탐색하여 각 역에서 순환선 내 가장 가까운 역과의 거리를 구하는 함수입니다.

 

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

public class Main{
	//간선 관련 생성자
	static class line{
		int station, count;
		public line(int station, int count) {
			super();
			this.station = station;
			this.count = count;
		}
	}
	static int N, start, end;
	static boolean[] cycle,visited;		//순환선 및 방문 확인 배열
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();	//역 관련 정보 저장
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		cycle = new boolean[N+1];
		for(int i=0;i<=N;i++)
			graph.add(new ArrayList<>());
			//역 관련 정보 저장
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
		visited = new boolean[N+1];
		dfs(1, 0);		//순환선 내 역을 찾는 DFS함수 실행
        	//각 역에서 순환선 내 역과의 최소 거리 구하기
		for(int i=1;i<=N;i++) {
			if(cycle[i])		//순환선 내 역일 때
				bw.write("0 ");
			else		//순환선 내 역이 아닐 때
				bw.write(bfs(i) + " ");
		}
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//순환선에 포함되는 역을 찾는 DFS 함수
	static void dfs(int cur, int previous) {
		visited[cur] = true;
		for(int next : graph.get(cur)) {
        		//방문했던 역 다시 방문해서 사이클 만들어졌을 때
			if(visited[next] && next != previous) {
				start = next;
				cycle[cur] = true;
				break;
			}
			
			if(!visited[next]) {
				dfs(next,cur);
                		//사이클 완성 시 사이클 내 역들 순환선에 포함
				if(cycle[next] && next!=start) {
					cycle[cur] = true;
					break;
				}
			}
		}
	}
    	//각 역에서 순환선 내 가장 가까운 역과의 거리 구하는 BFS 함수
	static int bfs(int start) {
		Queue<line> queue = new LinkedList<>();
		visited = new boolean[N+1];
		visited[start] = true;
		queue.add(new line(start, 0));
		while(!queue.isEmpty()) {
			line cur = queue.poll();
			if(cycle[cur.station])
				return cur.count;
			for(int next : graph.get(cur.station)) {
				if(!visited[next]) {
					visited[next] = true;
					queue.add(new line(next, cur.count+1));
				}
			}
		}
		return -1;
	}
}