Problem

문제 설명

출발 노드 S에서 도착 노드 E까지 도착하기 위한 최소 노드의 개수를 구한다. 이때 i번째 노드를 사용하지 못하는 경우를 각각 계산한다.

Submitted Code

접근법

후보1. BFS를 사용하면 E에 도착하기 위한 최소 노드의 개수를 구할 수 있다.

• i번째 노드를 사용하지 않는 경우를 계산하려면, 매번 BFS를 새로 계산해야 한다.
  • O(N * BFS 시간복잡도)로 시간 초과가 예상되지만, 가장 적절한 방법으로 판단하였다.

후보 2. 다익스트라를 응용한다.

	1	2	3	4
1	inf
2		inf
3			inf
4				inf

• 특정 노드를 경유할 때의 최소 거리를 계산할 수 있으므로, i번째 노드를 방문하지 않는 경우를 고려한다.
  • i번째 행에 대해 다익스트라를 시행할 때, 노드 i를 방문하지 못하는 것으로 설정한다. 하지만, 시간 복잡도가 N배 증가하므로 시간 초과가 예상된다.

Python

 1 from collections import deque
 2 import sys
 3 input = sys.stdin.readline
 4
 5 N, M, S, E = map(int, input().split())
 
 6 # 인접 리스트 생성
 7 roads = {i + 1: [] for i in range(N)}
 8 for _ in range(M):
 9     u, v = map(int, input().split())
10     roads[u].append(v)
11     roads[v].append(u)
12 
13 shortcuts = [0] + [N] * N                     # 최소 방문 노드의 개수를 저장
14 shortcuts[S] = shortcuts[E] = -1
15 left_nodes = set(roads.keys()) - set([S, E])  # 결정되지 않은 노드
16
17 queue = deque([[S]])
18 stack = set()
19 while left_nodes and queue:
       # BFS를 통해 탐색한 경로
20     path = queue.popleft()
21     node = path[-1]
22     path_nodes = set(path)   # 이미 방문한 노드를 확인하기 위해 set로 변경
23     for next_node in roads[node]:
24         next_node_set = set([next_node])
25         if len(path_nodes & next_node_set):
26             continue
27         if next_node == E:
28             avail_nodes = left_nodes - path_nodes
29             stack = stack | avail_nodes
30         else:
31             queue.append(path + [next_node])	
32     len_path = len(path) + 1
33     for node in stack:
34         shortcuts[node] = len_path
35         left_nodes.discard(node)
36     stack = set()
37
38 for s in shortcuts[1:]:	
39     print(s if s < N else -1)

Line 1

Code Review

 1 from collections import deque
 2
 3 def bfs(start, off):
 4     if start == off:
 5         return -1
 6 
 7     visited = [0] * (N + 1)
 8     q = deque([start])
 9     visited[start] = 1
10     step = 1
11
12     while q:
13         step += 1
14         for _ in range(len(q)):
15             now = q.popleft()
16
17             for to in graph[now]:
18                 if visited[to] or to == off:
19                     continue
20
21                 if to == E:
22                     return step
23
24                 visited[to] = 1
25                 q.append(to)
26	
27    return -1
28
29 N, M, S, E = map(int, input().split())
30 graph = [[] for _ in range(N + 1)]
31
32 for _ in range(M):
33     u, v = map(int, input().split())
34     graph[u].append(v)
35     graph[v].append(u)
36
37 for i in range(1, N + 1):
38     print(bfs(S, i))

Line 3-27

bfs(start, off) 함수를 정의한다.
start 인자는 시작 노드를, off 인자는 사용하지 않을 노드를 입력한다.

Line 4-5

start 노드와 off 노드가 같으면, -1을 출력한다.

Line 7

이미 방문한 노드를 visited 리스트에 기록한다.

Line 8-10

문제에 필요한 변수들을 초기화한다.

• Queue q에 출발 노드 start를 입력한다.
• visited 리스트에 출발 노드 start의 방문을 기록한다.
• BFS의 높이 step을 1로 초기화한다.
  • step 변수로 방문한 노드 개수를 확인하므로, start 노드를 포함한 개수로 초기화한다.

Line 12

이어진 노드가 존재할 때 while문을 반복한다.

Line 13

트리의 다음 높이로 이동하므로, step을 1만큼 증가시킨다.

Line 14

for-in 구문의 iterator range(len(q))는 for문을 시작할 때 생성된 후 값이 변하지 않는다. 반복문 실행 중에 len(q)가 변하더라도 생성된 iterator는 불변한다.

트리의 i번째 높이에 있는 노드만 확인하기

while queue:
    for _ in range(len(queue)):
        ...

Line 15

Queue q 맨 앞 쪽의 노드에 방문한다.

Line 17-25

현재 노드 now와 연결된 다음 노드 to에 대해 다음 동작을 수행한다.

Line 18-19

to 노드가 이미 방문한 노드이거나 사용하지 않을 노드 off이면 다음 for문을 수행한다.

Line 21-22

다음 노드 to가 도착 노드 E이면 트리의 높이(=방문한 노드 개수) step를 출력하고 함수를 종료한다.

다중 반복문 종료하기

def bfs(...):
    while queue:
        for _ in range(n):
            if end_condition:
                return ...
bfs(...)

Line 24-25

아직 E에 도착하지 못 한 경우, 다음 노드를 Queue q에 추가하고 visited 리스트에 방문을 기록한다.