2차 모의고사 1번 (정상화)

• 문제

문제에서 주의할 점이 있는데, K초 시점에서 힘이 다하므로 K-1초 시점에서 N-1번 집에 갈 수 없다면 -1을 반환해야 합니다.

먼저, 서로 그림자가 이어지는 것이 가능한 집들을 간선으로 이어 그래프를 구성합니다. 이때 간선들의 가중치는 두 집이 이어지기 위해 필요한 최소 시간으로 설정합니다.

이 그래프에서 prim 알고리즘으로 가중치가 최대한 작은 간선들을 사용해 0번 집에서 N-1번 집으로 가는 경로를 구성하면, 사용한 간선들의 가중치 중 최댓값이 문제의 답이 됩니다.

자세한 구현 과정은 다음과 같습니다.

• 0. 매크로와 구조체
• 1. 집들의 X좌표를 압축한 다음, 집들을 X좌표별로 나누고 Y좌표 순서대로 정렬해 저장합니다. 이때 집들에 입력받은 순서대로 번호를 부여해야 합니다.
• 2. 그림자가 이어지는 것이 가능한 집들을 잇습니다. 구현의 편의를 위해 (집 A의 Y좌표 ≤ 집 B의 Y좌표) 라 하면, A와 B가 이어질 조건은 (A와 B의 X좌표 차 == 1) && (B의 Y좌표 < A 바로 위 집의 Y좌표 - 1) 이 됩니다. 또, 이때 간선의 가중치는 두 집의 Y좌표 차가 됩니다. A보다 Y좌표가 작지 않은 집 B는 이분 탐색을 사용해 찾았습니다.
• 3. Prim 알고리즘으로 가중치가 최대한 작은 간선들만을 사용해 0번 집과 N-1번 집 사이 경로를 만듭니다. 이때 가중치가 K 미만인 간선만을 사용해야 합니다.
• 4. 찾은 경로를 백트래킹하며 가중치의 최댓값을 찾아 반환합니다. 찾은 경로가 없다면 -1을 반환합니다.