[Python] 14217번 그래프 탐색

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

14217번: 그래프 탐색

---

 

22/11/18

 

 

BFS문제로, 문제에서 주어지는 그대로 구현한다면 시간초과를 받을 수도 있는 문제다.

 

이를 유의하며 살짝 아이디어를 가져와야되는 문제다.

---

 

문제 접근 방식:

 

 

먼저 쿼리의 개수가 최대 $500$개이고, 도시(노드)의 개수가 총 $500$개라는 사실을 주목해보자.

 

때문에 문제에서 주어진 그대로 임의의 도시($k$번 노드)에서 수도 도시($1$번 노드)로 가는 최단 시간을 구하기 위해 BFS를 여러 번 돌린다면, $쿼리의 개수 * 도시의 개수$ $=$ $250,000$번 돌리게 된다.

 

때문에 만약 주어진 그대로 접근하게 된다면 시간초과가 난다.

 

 

여기서 떠올려야되는 핵심적인 아이디어는, BFS의 횟수를 줄이는 아이디어이다.

 

조금 생각해보면, 이 그래프는 양방향 간선을 가지고 있기 때문에 $k$번 노드에서 $1$번 노드로 가는 것이나, $1$번 노드에서 $k$번 노드로 가는 것이나 같은 최단시간, 최단 경로를 가지고 있다는 사실을 알 수 있다.

 

이를 이용하면 굳이 쿼리 하나마다 도시의 개수만큼 BFS를 돌리지 않고, 한 번만 돌려도 된다는 사실을 알 수 있다.

 

그렇다면, 먼저 시작노드가 $k$번 노드가 아닌 $1$번 노드, 다시 말해, 수도 도시에서 시작해야 된다는 결론까지 얻어낼 수 있다.

 

방문처리를 할 때, 방문처리 배열에 방문을 했던 시간을 담음으로써 각 도시별 최단시간을 구할 수 있다.

 

이를 반환함으로써 각 도시별 방문 시간을 쉽게 구할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 14217번 그래프 탐색
# 그래프 이론, 그래프 탐색, BFS
'''
접근 방법:
쿼리의 개수가 500개, 도시가 총 500개
BFS를 총 500*500번 = 250000번 돌린다.
일단 나이브 하게 BFS를 전부 다 돌려보자(실패함)
한 도시에서 수도 도시(1번 도시)로 가는데 BFS를 돌리는게 아니라
역으로 수도 도시(1번 도시)에서 BFS를 돌려보자.
그러면 BFS를 500*500번이 아닌 500번 돌리는 거랑 같다.
'''
import sys
from collections import deque
input = sys.stdin.readline

def BFS():
    visited = [-1 for _ in range(N+1)]  # 최소 시간을 저장하는 배열
    queue = deque()
    queue.append((1, 0))
    visited[1] = 0  # 수도 도시에서 수도 도시로 가는 최소 시간은 0
    while queue:
        node, time = queue.popleft()
        for near_node in graph[node]:
            if visited[near_node] == -1:
                visited[near_node] = time+1
                queue.append((near_node, time+1))
    return visited[1:]

N, M = map(int, input().rstrip().split())  # 도시 개수, 도로 개수
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

Q = int(input())  # 쿼리 개수

for _ in range(Q):
    a, i, j = map(int, input().rstrip().split())
    if a == 1:
        graph[i].append(j)
        graph[j].append(i)
        min_time_arr = BFS()
        print(*min_time_arr)
    else:
        graph[i].remove(j)
        graph[j].remove(i)
        min_time_arr = BFS()
        print(*min_time_arr)