[백준] 14621 나만 안되는 연애

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

각 노드들이 남초 대학교와 여초 대학교들끼리만 연결이 되어야 하므로, 링크를 저장하는 과정에서 서로 반대되는 경우에만 경로를 저장하였습니다.

2) 알고리즘

• 프림

3) 풀이 코드

사용 언어 - Python

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

def solution(start):
    heap = [(0, start)]                     # 시작 거리, 시작 노드

    while heap:
        node = heapq.heappop(heap)
        if not visited[node[1]]:            # 아직 방문하지 않은 학교인 경우
            visited[node[1]] = 1            # 방문 처리
            distance[node[1]] = node[0]     # 최소 거리 저장
            for e in linked[node[1]]:       # 현재 노드에서 다음으로 갈 수 있는 경로 최소힙으로 저장
                heapq.heappush(heap, e)


N, M = map(int, sys.stdin.readline().split())           # 학교의 개수, 도로의 개수
types = [''] + list(sys.stdin.readline().split())       # 학교 종류 리스트

linked = [[] for _ in range(N+1)]                       # 학교들 연결관계
distance = [0] + [1e10] * (N)                           # 학교들간 거리 리스트
visited = [0] * (N+1)                                   # 학교들 방문 여부

for _ in range(M):
    u, v, d = map(int, sys.stdin.readline().split())    # 출발 노드, 도착 노드, 거리
    
    if types[u] != types[v]:            # 서로 다른 종류의 학교인 경우
        linked[u].append((d, v))        # 양방향 저장
        linked[v].append((d, u))

solution(1)                 # 탐색

if sum(visited) == N:       # 모든 학교가 이어진다면 연결된 최소 거리 반환
    print(sum(distance))
else:                       # 모든 학교가 연결되지 않는다면 -1 출력
    print(-1)

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

14621번: 나만 안되는 연애

 

 

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