서울 지하철 2호선(16947번) - 파이썬(Python)

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

16947번: 서울 지하철 2호선

문제

서울 지하철 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:])))