[백준] 2211 네트워크 복구

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

컴퓨터들간의 연결 관계를 기록하고, 1번 컴퓨터를 시작으로 다른 컴퓨터에 도달 가능한 최소 거리들을 구해야 하므로 다익스트라를 이용하였습니다.

다익스트라 탐색 시, 출발 노드와 도착 노드를 기록하여 어떤 회선을 복구하였는지 기록하였습니다.

2) 알고리즘

• 다익스트라

3) 풀이 코드

사용 언어 - Python

import sys
import heapq
sys.stdin = open('input.txt')

def solution(start):
    h = [(0, start, start)]                                 # 거리, 도착 컴퓨터 번호, 출발 컴퓨터 번호

    while h:
        node = heapq.heappop(h)
        if distance[node[1]] == -1:                         # 컴퓨터 거리 탐색 안되었다면
            distance[node[1]] = node[0]                     # 최소 거리 기록
            answer.append((node[2]+1, node[1]+1))           # 출발 컴퓨터 번호, 도착 컴퓨터 번호 기록
            for next in linked[node[1]]:                    # 현재 컴퓨터와 연결된 다음 컴퓨터들 거리 추가하여 탐색
                heapq.heappush(h, (node[0] + next[0], next[1], node[1]))

N, M = map(int, sys.stdin.readline().split())               # 컴퓨터 개수, 회선(연결) 개수
linked = [[] for _ in range(N)]                             # 컴퓨터간 연결 정보
distance = [-1] * N                                         # 각 컴퓨터간 통신 최소 시간
answer = []                                                 # 복구할 회선 정보

for _ in range(M):
    A, B, C = map(int, sys.stdin.readline().split())
    linked[A-1].append((C, B-1))                            # 양방향 통신이므로 두 컴퓨터에 연결 관계 기록
    linked[B-1].append((C, A-1))

solution(0)                                                 # 1번 컴퓨터 보안 시스템 설치

print(len(answer)-1)
for i in range(1, len(answer)):
    print(*answer[i])

---

🔗 문제 링크

- https://www.acmicpc.net/problem/2211

2211번: 네트워크 복구

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다