[ICPC 본선 대비 뇌셋] Day 5

백준 17970번 Islands www.acmicpc.net/problem/17970

17970번: Islands

증명이 까다롭기는 하나 그렇게까지 어려운 문제는 아닌 것 같다. 사실상 왜 다이아 2인지는 잘 모르겠다. 물론 작년의 나는 못풀었다.ㅋㅋ

convex를 그냥 cycle로 바꿔 생각해도 무방하다. 편의상 a, b가 인접해있다는 것을 두 섬에서 모두 바로 옆에 붙어있는 점들, 인접한 그룹들은 두 섬에서 모두 두 그룹들의 점들 사이에 다른 점이 없는 그룹(마찬가지로 바로 옆에 붙어있는 경우)으로 정의하자.

[관찰 1] sequence의 시작점은 무조건 원에서 인접한 점을 가지고 있을 것이다.

관찰 1로부터, 우리는 인접한 점들을 묶어간다면 문제가 풀릴 것이라는 상상을 할 수 있다.

[가설 1] 인접한 그룹들을 Union find 해주면서 계속해서 묶어 나갈때 모든 점을 묶을 수 있으면 그 과정을 역추적 했을 때 Sequence를 재구성 할 수 있다.

가설 1은 아주 강력해보이지만, N = 9인 경우를 조금만 생각하면 반례를 찾을 수 있다.

두 섬의 번호가 검은색 숫자로 매겨져있는 경우, 빨간색 간선의 순서대로 그룹을 합칠 수 있다. 마지막에는 두 섬 모두 위, 아래 그룹으로 나뉘며, 가설 1에서 이 두개의 그룹은 '인접한 그룹'이지만, 두개의 그룹을 양쪽 섬 모두에서 교차하지 않도록 연결하는 것은 불가능하다. 이 경우를 제외하고도 이러한 점 배치에서 Sequence를 구성하는 것은 불가능하다.

따라서 관찰 1의 제약조건을 조금 더 강화시킬 필요가 있다.

[관찰 2] (처음에는 그룹 -> 점으로 시작한 관찰이다.) Sequence가 존재한다고 가정하자. 그렇다면 그룹 1과 그룹 2가 각각 [가설 1]에서 만들어진 그룹이고 서로 인접해있다면 그룹 1과 그룹 2를 연결한 Sequence가 존재한다.

[증명] 수학적 귀납법. 점 두개일 경우에는 아래의 증명과 동일하게 증명 가능하다. [가설 1]에서 k-1 번째로 두 그룹을 묶었을 때 관찰 2가 성립되었다고 가정하자. [가설 1]에서 k번째로는 그룹 1과 그룹 2를 연결하려고 할 때, 그룹 1과 그룹 2가 직접적으로 연결되어있는 Sequence가 존재함을 증명하자.

Figure1. 빨간색 간선은 그래프를 바꾸기 이전의 모습, 파란색 간선은 그래프를 바꾼 다음의 모습이다.

(Note. 위의 그림에서 빨간색 그래프에 Group에 연결된 간선이 하나인 경우에도 비슷한 방법으로 증명할 수 있다.)

먼저 빨간색 그래프(k-1번의 귀납을 통해 만들어진 sequence)를 보자. 섬 1에서 a, b, c, d의 순서로 되어있다면, b, c사이가 간선들로 연결되어있을 것이다. 마찬가지로 섬 2에서도 b, c가 간선들로 연결되어있을 것이므로, 순서는 a, b, c, d또는 그 반대가 될 것이다. 어떤 경우이든 위 빨간색 간선들을 파란색 간선들로 바꿔줄 수 있다. 파란색 선이 다른 선과 교차하지 않음과, 새로운 그래프가 sequence임은 자명. 증명됨. (두 그룹에서 밖으로 나오는 선들 중 가까운 점들이 새로 연결됐음에 주의하라.)

따라서 우리는 가설 1을 따라서 연결하려고 하는 그룹의 끝점들 중 Adjecent부분과 가장 가까운 두 부분을 잇도록 하는 코드를 짜면 된다. 만약 이 과정을 통해서 두 정점을 이을 수 없다면(교차한다면) -1을 출력하면 된다.

[코딩] union find를 통해 두 그룹이 인접한지를 판단한다.

처음 한바퀴를 돌면서 인접한 두 점을 체크하고 각 그룹 쌍을 Queue에 넣는다.

Queue가 비어질때까지 다음과정을 수행한다.

1. Queue에서 뽑은 한 쌍의 그룹에 대해서 위에서 제시한 규칙으로 간선을 잇는다. 잇지 못하면 -1을 출력한다.

2. 빠져나간 쌍의 양 옆에서 인접한 쌍이 존재하는지 확인한다. 존재하면 Queue에 넣는다.

중복되는 쌍은 잘 관리한다.

증명을 써보니 뭔가 어려운 것 같기도 하네..