[백준/파이썬][Silver I] 그래프 탐색 2 - 14218

[Silver I] 그래프 탐색 2 - 14218

문제 링크

성능 요약

메모리: 115600 KB, 시간: 232 ms

분류

너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2025년 2월 3일 18:31:45

문제 설명

남규나라의 왕 zych는 도로 정비 계획을 발표하였다. 두 도시를 있는 도로들을 새로 만드는 계획이다. 도로 정비 계획은 두 도시에 대한 정보가 주어지는데, 도로를 정비하는 일은 매우 큰 일이기에 계획을 순서대로 하나씩 시행해 나갈 것이다.

Zych는 차후 도로 정비 계획에 참고하기 위하여, 각 도시들이 수도에 방문하는데 최소 몇 개의 도시들을 방문해야 하는지 조사하기로 하였다.

남규나라의 초기 도시상태가 주어지고 도로 정비계획이 주어질 때, 한 도로가 정비될 때마다 각 도시별로 수도를 방문하는 데 최소 방문 도시들을 출력하시오.

입력

첫째 줄에는 도시의 개수 n,도로의 개수 m이 주어진다. 다음 m개의 줄에는 두 도시가 주어진다.(2≤n≤1,000,1≤m≤100,000)

다음 줄에는 도로 정비 계획에 들어가 있는 도로의 수 q가 주어지고, 다음 q줄에는 i j가 주어지는데 두 도시 i,j를 잇는 도로를 만든다.. (1≤q≤500, 1≤i,j≤n)

수도는 1번도시이다.

출력

q줄에 각 도시별로 수도를 방문하는 데 최소 방문 도시들을 출력하시오. 만약 수도를 방문하지 못한다면 -1을 출력하시오.

풀이

from collections import deque

def bfs(s) :
    '''
    :param s: 이 노드부터 탐색을 시작할 것이다.
    :return: list
    BFS를 사용하여 시작점 s에서 모든 노드까지의 최단 거리를 계산하는 함수
    '''
    q = deque()
    q.append(s)
    distances = [-1] * (n + 1)  # 모든 노드의 거리를 -1로 초기화 (방문하지 않음)
    distances[s] = 0    # 시작 노드 거리 초기화

    while q :
        c = q.popleft()

        for nxt in edges[c] :
            dist = distances[c] + 1
            if distances[nxt] == -1 :
                distances[nxt] = dist
                q.append(nxt)

    return distances[1:]


n, m = map(int, input().split())
edges = [[] for _ in range(n + 1)]
for _ in range(m) :
    u, v = map(int, input().split())
    edges[u].append(v)
    edges[v].append(u)

bridges = int(input())
for _ in range(bridges) :
    u, v = map(int, input().split())
    edges[u].append(v)
    edges[v].append(u)
    res = bfs(s=1)
    print(*res)

얼핏 보면 다익스트라 알고리즘같기도 하다. 실제로 다익스트라 알고리즘으로 해결이 가능한 문제이기도 하지만, 도달하지 못할 경우, -1로 처리하는 조건을 보고 BFS로 풀이를 진행하였다.

다익스트라 알고리즘으로 풀이를 할 경우에는 무한대나 아주 큰 수를 distances 인자로 넣어준 뒤에 여전히 그 값이면 -1로 바꿔주면 쉽게 풀이가 가능할 것이다. 실제로 그렇게 풀어보았다. 

import heapq

INF = 1001

def djikstra(start) :
    q = []
    distances = [INF] * (n + 1)
    distances[start] = 0
    heapq.heappush(q, (0, start))   # dist, start

    while q :
        dist, curr = heapq.heappop(q)
        if distances[curr] < dist :
            continue

        for nxt in edges[curr] :
            nxt_dist = dist + 1
            if distances[nxt] > nxt_dist :
                distances[nxt] = nxt_dist
                heapq.heappush(q, (nxt_dist, nxt))

    return distances


n, m = map(int, input().split())
edges = [[] for _ in range(n + 1)]

for _ in range(m) :
    u, v = map(int, input().split())
    edges[u].append(v)
    edges[v].append(u)

distances = djikstra(1)
bridges = int(input())
output = []
for _ in range(bridges) :
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)
    distances = djikstra(1)
    for i in range(n + 1) :
        if distances[i] == INF :
            distances[i] = -1
    print(*distances[1:])

이것도 나쁘진 않았지만 답 처리 할 때 복잡한 면이 있었다. 둘 다 원하는 대로 풀이를 하시면 될 듯 하다.

글을 잘 읽어야 한다는 것을 느낄 수 있었다.

1. 지금 설치되어 있는 다리를 edges 에 넣는다.
2. 다리를 하나씩 설치하면서 거리가 어떻게 변하는지 distances 를 통하여 결과를 return 하면 된다.
3. 마지막으로, 다리를 다시 철거하는게 아니기 때문에 하나씩 쌓여간다고 생각하면 된다. 

BFS와 다익스트라 알고리즘은 방문 처리를 어떻게 할 것이냐, 그리고 자료구조를 deque이냐 heap 이냐 의 차이기 때문에 이 차이점만 인지한다면 무난하게 풀 수 있는 문제라고 생각한다. 

사실 처음 풀때는 이해가 잘 되지 않았는데, 다른 분의 풀이를 조금 보고 이해할 수 있었다.