[Baekjoon] 서울 지하철 2호선
Updated:
문제
서울 지하철 2호선은 다음과 같이 생겼다.
지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.
두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.
지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.
입력
첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.
출력
총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, …, N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.
예제
Example 1:
Input:
4
1 3
4 3
4 2
1 2
Output:
0 0 0 0
Example 2:
Input:
6
1 2
3 4
6 4
2 3
1 3
3 5
Output:
0 0 0 1 1 2
Example 3:
Input:
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
Output:
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
Example 4:
Input:
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
Output:
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
Example 5:
Input:
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
Output:
2 2 1 0 0 0 0 0 1 1 2 2
조건
시간 제한 : 2초
메모리 제한 : 512 MB
풀이과정
풀이 1
사이클을 구한 뒤, 거기서 사이클이 아닌 선과의 거리를 구한다. 사이클을 구할 때는 dfs, 거리를 구할 때는 bfs를 사용하였다. 사이클을 구하는 것에 대해 굉장히 고민을 했는데 아래처럼 일일이 다 dfs해주면 시간 초과가 뜨기 때문이다. 하지만 아직 적절한 방법을 찾지 못하였다.
from collections import deque
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n+1)]
cycle = []
for _ in range(n):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
visited = [False] * (n + 1)
def dfs(start, here, level):
if level <= 2:
for v in graph[here]:
if visited[v] == False:
visited[v] = True
dfs(start, v, level+1)
visited[v] = False
else:
for v in graph[here]:
if visited[v] == False:
visited[v] = True
dfs(start, v, level+1)
visited[v] = False
else:
if v == start:
cycle.append(start)
return
for i in range(1, n+1):
visited[i] = True
dfs(i, i, 1)
visited[i] = False
# bfs 수행
answer = [int(1e9)] * (n + 1)
q = deque()
for c in cycle:
q.append((c, 0))
answer[c] = 0
while q:
node, level = q.popleft()
for v in graph[node]:
if answer[v] == int(1e9):
answer[v] = level+1
q.append((v, level+1))
print(" ".join(map(str, answer[1:])))
풀이 2
사이클이 하나만 존재한다는 사실을 간과했다… 이러면 문제는 간단해진다. dfs를 통해 사이클을 발견하면 사이클을 저장하고 거기서 bfs를 수행한다. 문제를 똑바로 읽자..
from collections import deque
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n+1)]
cycle = set()
for _ in range(n):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
visited = [False] * (n + 1)
cy = False
def dfs(start, here, level, li):
global cy
if level <= 2:
for v in graph[here]:
if visited[v] == False:
visited[v] = True
dfs(start, v, level+1, li+[v])
visited[v] = False
else:
for v in graph[here]:
if visited[v] == False:
visited[v] = True
dfs(start, v, level+1, li+[v])
visited[v] = False
else:
if v == start:
cy = True
for l in li:
cycle.add(l)
return
for i in range(1, n+1):
if cy == True:
break
visited[i] = True
dfs(i, i, 1, [i])
visited[i] = False
cycle = list(cycle)
# bfs 수행
answer = [int(1e9)] * (n + 1)
q = deque()
for c in cycle:
q.append((c, 0))
answer[c] = 0
while q:
node, level = q.popleft()
for v in graph[node]:
if answer[v] == int(1e9):
answer[v] = level+1
q.append((v, level+1))
print(" ".join(map(str, answer[1:])))
Leave a comment