[BOJ/Python] 17490_일감호에 다리 놓기

문제 출처:https://www.acmicpc.net/problem/17490

17490번: 일감호에 다리 놓기

문제

학교의 홍보대사를 맡게 된 건덕이는 건국대학교의 모든 강의동을 신입생들에게 소개해야 한다.

건국대학교 중앙에 위치한 일감호를 따라 한 바퀴를 돌며 모든 강의동을 소개하는 것이 그의 일이지만, 몇몇 구간들이 공사 중이어서 그 구간을 통해서는 갈 수 없는 상황이다. 급한대로 건덕이는 호수에 돌을 던져 징검다리를 놓아 길을 만들어보려고 한다.

강의동은 일감호의 둘레에 따라 원형으로 배치돼 있으며, 강의동 양 옆의 강의동은 서로 이웃한다. 또, 원형으로 배치돼 있기 때문에 N개의 강의동이 있다면 N번째 강의동과 1번째 강의동은 서로 이웃한다.

일감호 안에는 와우도라는 섬이 있다. 건덕이는 한 강의실에서 다른 모든 강의실로 이동할 수 있도록 강의동에서 와우도까지 징검다리를 놓기로 했다. 하지만 건덕이의 눈에는 K개의 돌밖에 보이지 않는다. 건덕이는 주어진 돌을 활용해서 징검다리를 완성할 수 있을까?

입력

첫째 줄에 강의동의 수 N, 공사구간의 수 M, 건덕이가 가진 돌의 수 K가 공백으로 구분돼 주어진다. 강의동은 1동부터 N동까지 존재한다.

다음 줄에는 강의동에서 와우도까지 놓아야하는 돌의 개수 S1, S2, ..., SN이 공백으로 구분돼 주어진다. 이는 T번째 강의동에서 와우도까지 ST개의 돌을 놓아야 함을 의미한다. 이어서 M개의 줄에 i, j가 주어진다. 이는 i번째 강의동에서 j번째 강의동까지 가는 길이 공사중임을 의미한다. 이 때 입력되는 i, j번째 건물은 이웃한 강의동이다. 공사중인 구역은 한 번만 주어진다.

출력

건덕이가 가지고 있는 돌을 놓아 모든 강의동을 연결할 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.

제한

• 3 ≤ N ≤ 1,000,000
• 0 ≤ M ≤ N
• 1 ≤ i, j ≤ N 
• 1 ≤ T ≤ N인 모든 정수 T에 대해 1 ≤ ST ≤ 1,000,000
• 0 ≤ K ≤ 5,000,000,000

예제 입력 1

5 3 9
2 1 3 2 5
2 3
4 5
5 1

예제 출력 1

YES

2번, 4번, 5번 강의동과 와우도를 연결하면 가지고 있는 돌 내에서 징검다리를 완성할 수 있다. 이 때, 어떤 한 강의동에서 다른 모든 강의동으로 가는 길이 존재한다.

 

예제 입력 2 

5 3 7
2 1 3 2 5
2 3
4 5
5 1

예제 출력 2 

NO

---

풀이

 

문제를 요약하면 다음과 같다.

 

1. 1번 강의동 부터 N번 강의동까지 존재한다. (N개의 노드)
2. 1번 강의동은 2번 강의동과 인접하고, 2번 강의동은 3번 강의동과 인접하고, ... , N번 강의동은 1번 강의동과 인접한다.
3. 강의동에서 다른 강의동으로 이동하려고 한다.
4. 이때, 두 강의동 사이가 공사를 하게 될 수 있고, 직접 이동이 불가능한 경우 와우도를 통해 이동할 수 있다.
5. 강의동에서 와우도 까지는 징검다리를 만들어 이동할 수 있으며, 징검다리에 필요한 돌의 개수는 강의동마다 다르다.
6. 보유한 돌의 개수로 징검다리를 만들어 모든 강의동을 연결할 수 있으면 YES를 아니라면 NO를 출력하는 문제이다.

 

문제를 해결하기 위해 union&find를 이용하였다.

1. 우선 공사중인 강의동이 하나도 없다면, 모든 강의동이 연결되어 있으므로 YES를 출력한다. (한 강의동에서 다른 모든 강의동으로의 이동이 가능하기 때문이다.)
2. 또한, 공사중인 강의동이 하나일 경우에도 모든 강의동이 연결되어 있다고 할 수 있다. (강의동이 원형으로 배치되어 있으므로, 반대편으로 돌아가면 공사중인 강의동으로 이동할 수 있다.)
3. 만약 공사중인 강의동이 둘 이상이라면, 와우도를 거쳐서 이동하여야 한다.
4. union&find를 이용하여, 공사중인 강의동을 제외한 나머지 인접한 강의동들끼리 하나의 집합으로 연결한다.
5. 예를 들어, 강의동이 1번부터 5번까지 존재하고, (2 - 3) , ( 4 - 5) 가 공사중이라면, (1-2), (3-4), (5-1)의 집합이 되고, (1-2), (5-1) 또한 같은 집합이므로, (1-2-5), (3-4) 의 두 집합으로 나뉘게 됨을 알 수 있다.
6. 여기서 (1-2-5) 집합에서 징검다리를 만드는데 필요한 돌의 최소의 개수 + (3-4) 집합에서 징검다리를 만드는데 필요한 돌의 최소의 개수를 더한다.
7. 이 값이 갖고 있는 돌의 개수보다 크다면 모든 강의동을 연결할 수 없으므로 NO를 출력하고, 같거나 작다면 징검다리를 만들어 모든 강의동을 연결할 수 있으므로 YES를 출력한다.

 

코드는 다음과 같다.

 

import sys
sys.setrecursionlimit(int(1e6))
 
def find_parent(parent,x):
    if parent[x] != x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]
 
def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
 
    if a<b:
        parent[b] = a
    else:
        parent[a] = b
 
 
n,m,k = map(int,sys.stdin.readline().split())
parent = [i for i in range(n+1)]
 
stones = list(map(int,sys.stdin.readline().split()))
unable_move = set()
for _ in range(m):
    a,b = map(int,sys.stdin.readline().split())
    a,b = min(a,b),max(a,b)
    unable_move.add((a,b))
 
ans = "YES"
if m>1:
 
    for i in range(1,n):
        if (i,i+1) not in unable_move:
            union_parent(parent,i,i+1)
 
    if (1,n) not in unable_move:
        union_parent(parent,1,n)
 
    result = dict()
 
    for i in range(1,n+1):
        p = find_parent(parent,i)
        if p not in result:
            result[p] = stones[i-1]
        else:
            result[p] = min(result[p], stones[i-1])
 
    if sum(result.values()) > k:
        ans = "NO"
 
print(ans)