그래프 탐색 - 백준 #14217, 골드5, 그래프/너비 우선 탐색

문제 링크

14217번: 그래프 탐색

풀이

from collections import deque
import sys

def bfs():
    visited = [-1]*(n_city+1)
    visited[1] = 0    # 수도: 1번 도시
    queue = deque()
    queue.append(1)
    while queue:
        loc = queue.popleft()    # 현 위치
        for next_loc in road[loc]:    # 갈 수 있는 곳
            if visited[next_loc] == -1:
                visited[next_loc] = visited[loc]+1
                queue.append(next_loc)
    return visited[1:]


# 입력 받기
input = sys.stdin.readline
n_city, n_road = map(int, input().split())

road = [[] for _ in range(n_city+1)]
for _ in range(n_road):
    city1, city2 = map(int,input().split())
    road[city1].append(city2)
    road[city2].append(city1)

n_plan = int(input())
for _ in range(n_plan):
    plan, city1, city2 = map(int,input().split())
    if plan == 1:    # 도로 만들기
        road[city1].append(city2)
        road[city2].append(city1)
    else:    # plan ==2 도로 없애기
        road[city1].remove(city2)
        road[city2].remove(city1)

    result = bfs()
    print(*result)