[백준/1045] 도로 (Python)

Problem : https://www.acmicpc.net/problem/1045

1045번: 도로

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:17:57

 

---

 

문제 설명

 

 

0부터 N-1까지의 번호가 매겨져 있는 N개의 도시와 두 도시를 연결하는 도로가 있다. 도로에는 우선순위가 있는데, A와 B가 (A < B) 도로 x로 연결되어 있고, C와 D가 (C < D) 도로 y로 연결되어 있을 때, 튜플 (A, B) < (C, D)이면 x > y, 즉 x의 우선순위가 더 높다. 여기서 ai ≠ bi인 가장 작은 양의 정수 i에 대해 ai < bi이면 (a1, ..., ak) < (b1, ..., bk)로 정의한다.

도로의 집합은 하나 이상의 도로가 우선순위에 대한 내림차순으로 정렬되어 있는 것이다. 집합 사이에도 우선순위가 있는데, 두 집합을 튜플로 나타냈을 때의 우선순위를 따른다. 한 집합에 있는 도로만으로 임의의 도시에서 임의의 도시로 이동할 수 있을 때, 그 집합은 연결되어 있다고 한다.

김지민이 할 일은 M개의 도로를 가진 도로의 집합 중 연결되어 있으면서 우선 순위가 가장 높은 것을 찾는 것이다.

 

 

입력 및 출력

 

입력

 

첫째 줄에 도시의 개수 N과 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N-1보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 둘째 줄부터 N개의 줄에는 인접행렬이 주어진다. 즉 i번째 행의 j번째 열이 Y이면 도시 i와 j를 연결하는 도로가 존재하고, N이면 존재하지 않는다. i와 j가 연결되어 있으면 j와 i도 연결되어 있음이 보장되고, i와 i는 연결되어 있지 않다.

 

출력

 

만약 정답이 없을 때는 -1을 출력한다. 정답이 존재하면, 그 집합에 속하는 도로 중 0을 끝점으로 갖는 도로의 개수, 1을 끝점으로 갖는 도로의 개수, ..., N-1을 끝점으로 갖는 도로의 개수를 차례로 출력한다.

 

입력 예시

 

3 2
NYY
YNY
YYN

 

출력 예시

 

2 1 1

 

 

---

 

풀이

 

그리디하게 접근해 보자.

 

• 우선, 모든 도시가 연결되어 있어야 하며, 그 도시를 잇는 간선은 M개여야 한다.
• 즉 N-1개의 가장 우선도가 낮은 튜플로 MST를 구성하고, 남은 간선들 중 (M - N + 1)개의 우선도가 낮은 튜플을 뽑아 그래프에 추가한다.
• 즉 MST 알고리즘 역시 사용된다.
  • 이 때, 그래프에 추가되는 두 도시의 값을 1씩 증가시킴으로써 해를 구성할 수 있다.
• MST를 만들지 못하는 경우, 혹은 가능한 모든 간선을 전부 추가했을 때 M개 간선을 이루지 못하는 경우에 한하여 -1을 출력한다.

 

풀이 코드

from heapq import *
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
cnt = 0
edge_q = []
left_q = []
ans = [0]*N
parents = list(range(N))

for i in range(N) :
  maps = input().strip()
  for j in range(i+1, N) :
    if maps[j] == 'Y' :
      heappush(edge_q, (i, j))

def find(a) :
  if parents[a] == a :
    return a
  parents[a] = find(parents[a])
  return parents[a]

def union(pa, pb) :
  if pa > pb :
    pa, pb = pb, pa
  parents[pb] = pa

while edge_q and cnt < M :
  a, b = heappop(edge_q)
  pa, pb = find(a), find(b)
  if pa == pb :
    heappush(left_q, (a, b))
    continue
  union(pa, pb)
  cnt += 1
  ans[a] += 1
  ans[b] += 1
if cnt < N-1 :
  print(-1)
  exit()
while left_q and cnt < M :
  a, b = heappop(left_q)
  ans[a] += 1
  ans[b] += 1
  cnt += 1
print(*(ans if cnt == M else [-1]))

풀이 완료!