[BOJ] 백준 14218번 그래프 탐색 2 | python 파이썬 코드, 해설, 풀이

백준 14218번 그래프 탐색 2 문제 파이썬 풀이입니다.

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

14218번: 그래프 탐색 2

실버1 치고는 널널한? 문제였습니다. N이 1000이라 최적화없이 대충짜도 어째저째 돌아가는 문제였습니다.

 

INF로 초기화 시킨 distance 배열을 만들어 두고, 테스트가 들어올 때마다 node 1에서 시작해서 BFS를 돌며 최소거리로 갱신시켜 나가는 방식으로 해결할 수 있었습니다.

 

주요코드

line 19 ~ 31 : 1부터 시작해서 각 node까지 BFS를 도는데, path에 0부터 시작해서 다음 node를 호출할 때마다 1씩 더한값을 queue에 넣는다. 이때 path와 distance array를 비교하면서 더 작은 값(짧은 거리)으로 distance array를 갱신시킨다.

 

전체코드

import sys
from collections import deque
 
input = sys.stdin.readline
 
n, m = map(int, input().split())
INF = 1001
L = [[0] * (n + 1) for _ in range(n + 1)]
distance = [INF for _ in range(n + 1)]
distance[1] = 0
 
for _ in range(m):
    a, b = map(int, input().split())
    L[a][b] = 1
    L[b][a] = 1
t = int(input())
 
 
def bfs(target):
    visited = [False for _ in range(n + 1)]
    queue = deque()
    queue.append(target)
    while (queue):
        node, path = queue.popleft()
        if (distance[node] > path):
            distance[node] = path
        visited[node] = True
        for i in range(len(L[node])):
            if (L[node][i] == 1 and visited[i] == False):
                queue.append([i, path + 1])
                visited[i] = True
 
 
for _ in range(t):
    a, b = map(int, input().split())
    L[a][b] = 1
    L[b][a] = 1
    bfs([1, 0])
    for i in range(1, n + 1):
        if (distance[i] == INF):
            print(-1, end=" ")
        else:
            print(distance[i], end=" ")
    print()