문제
서울 지하철 2호선은 다음과 같이 생겼다.
지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.
두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.
지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.
입력
첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.
출력
총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, ..., N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.
예제 입력 1
4
1 3
4 3
4 2
1 2예제 출력 1
0 0 0 0예제 입력 2
6
1 2
3 4
6 4
2 3
1 3
3 5예제 출력 2
0 0 0 1 1 2예제 입력 3
51
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 1
11 44
44 45
45 46
46 47
34 48
48 49
49 50
50 51예제 출력 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 1 2 3 4예제 입력 4
38
1 2
2 3
3 4
4 5
5 6
6 1
1 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38예제 출력 4
0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32예제 입력 5
12
1 3
3 4
4 5
5 6
6 7
7 8
8 4
2 3
7 9
9 12
7 10
10 11예제 출력 5
2 2 1 0 0 0 0 0 1 1 2 2풀이
이 문제는 그래프의 사이클을 구하는 문제이다. 그래프의 사이클 구하기 위해 DFS 알고리즘을 이용했고 순환역까지 가는 거리는 BFS 알고리즘을 이용해서 구할 수 있었다.
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
static ArrayList<Integer>[] map;;
static int N;
static boolean[] cycle;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new ArrayList[N+1];
for(int i=1; i<=N; i++)
map[i] = new ArrayList<>();
cycle = new boolean[N+1];
int[] ans = new int[N+1];
for(int i=0; i<N; i++) {
String[] input = br.readLine().split(" ");
int start = Integer.parseInt(input[0]);
int end = Integer.parseInt(input[1]);
map[start].add(end);
map[end].add(start);
}
for(int i=1; i<=N; i++) {
if(isCycle(i, i, i))
break;
else
cycle = new boolean[N+1];
}
for(int i=1; i<=N; i++) {
if(cycle[i]) continue;
int cnt = bfs(i);
ans[i] = cnt;
}
for(int i=1; i<=N; i++)
System.out.print(ans[i]+" ");
}
public static boolean isCycle(int before, int v, int start) {
cycle[v] = true;
for(int i=0; i<map[v].size(); i++) {
int e = map[v].get(i);
if(!cycle[e]) {
if(isCycle(v, e, start))
return true;
}
else if(e!=before && e==start)
return true;
}
cycle[v] = false;
return false;
}
public static int bfs(int v) {
Queue<Pair> queue = new LinkedList<>();
boolean[] visited = new boolean[N+1];
queue.add(new Pair(v, 0));
visited[v] = true;
while(!queue.isEmpty()) {
Pair temp = queue.poll();
if(cycle[temp.v])
return temp.cnt;
for(int i=0; i<map[temp.v].size(); i++) {
int e = map[temp.v].get(i);
if(!visited[e]) {
visited[e] = true;
queue.add(new Pair(e, temp.cnt+1));
}
}
}
return 0;
}
public static class Pair {
int v;
int cnt;
public Pair(int v, int cnt) {
this.v = v;
this.cnt = cnt;
}
}
}
👶🏻Jr. Programmer