[BOJ]17490번: 일감호에 다리 놓기

 

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

---

UNION & FIND 문제입니다.

 

M개의 공사구간이 있으면 강의동은 M개의 컴포넌트로 나뉘게 됩니다.

 

1. M개의 컴포넌트로 나누기 (O(N))

2. 각 컴포넌트마다 다리를 놓는데 최소비용인 강의동 구하기(O(N))

3-1. M개의 컴포넌트의 각 최솟값들의 합 <= K 이면, YES

3-2. M개의 컴포넌트의 각 최솟값들의 합 > K 이면, NO

 

연결상태는 graph[N][2]를 통해 표현하였습니다.

graph[idx][0] = 1이면, idx번째 강의동이 idx-1 강의동과 끊어져 있음.

graph[idx][1] = 1이면, idx번째 강의동이 idx+1 강의동과 끊어져 있음.

(단, 원형이므로 0번째 강의동과 N-1번째 강의동의 연결관계는 반대로 처리해줘야 합니다)

 

끝으로 예외 처리해줄 것은 M <= 1 이면 무조건 모든 강의동을 이동할 수 있습니다.

visited 배열을 통해 모든 강의동은 딱 한 번만 방문하므로 시간복잡도는 O(N)에 처리할 수 있습니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ17490.cc