[백준] 일감호에 다리 놓기

https://www.acmicpc.net/problem/17490

17490번: 일감호에 다리 놓기

 

정답률이 매우 낮아서 걱정했지만 생각보다 그리 어렵지않게 풀 수 있었던 문제입니다. 원형으로 이어져있는 그래프에서 각각의 연결 그래프를 이루고 있는 강의동들 중 가장 작은 돌다리가 필요로하는 강의동에만 연결해주면 됩니다. 이렇게 했을 때에 K개를 넘어가면 불가능하므로 NO를 출력해주면 됩니다. 조심해야하는 점은 돌다리를 놓지 않고도 연결되어 있는 경우가 있습니다. 정답률이 낮은 이유는 아마도 C++이나 JAVA에서 long 대신 int를 써서 그렇지 않을까? 라고 생각이 들긴 합니다.

 

import sys
from collections import defaultdict, deque

# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

# n: 강의동의 수, m: 공사구간의 수, K: 건덕이가 가진 돌의 수
n, m, k = tuple(map(int, input().split()))

rocks = list(map(int, input().split()))

# 인접리스트로 그래프 구축
# graph[i][0], [1] 0 왼쪽 1 오른쪽
graph = [
    [True] * 2
    for _ in range(n + 1)
]

for _ in range(m):
    num, num2 = tuple(map(int, input().split()))

    minNum = min(num - 1, num2 - 1)
    maxNum = max(num - 1, num2 - 1)

    if minNum == 0 and maxNum == n - 1:
        graph[0][0] = False
        graph[n - 1][1] = False
    else:
        graph[minNum][1] = False
        graph[maxNum][0] = False

def bfs(start):
    q = deque([start])
    visited[start] = True
    minRock = sys.maxsize

    while q:
        cur = q.popleft()


        minRock = min(rocks[cur], minRock)

        left, right = (cur + n - 1) % n, (cur + 1) % n

        # 왼쪽으로 이동
        if graph[cur][0] == True and not visited[left]:
            q.append(left)
            visited[left] = True

        # 오른쪽으로 이동
        if graph[cur][1] == True and not visited[right]:
            q.append(right)
            visited[right] = True

    return minRock

visited = [False] * (n + 1)

bfs(0)

flag = True

# 돌다리를 두지 않아도 연결되어 있는지 확인
for i in range(0, n):
    if visited[i] == False:
        flag = False
        break

if flag:
    print("YES")
    sys.exit(0)

visited = [False] * (n + 1)

for i in range(0, n):
    # 한 연결 그래프에서 최소 돌만 연결하면 된다.
    if not visited[i]:
        ret = bfs(i)
        k -= ret
        if k < 0:
            print("NO")
            sys.exit(0)

print("YES")