ICPC 2019 Seoul Regional C번 Islands

문제 링크: https://www.acmicpc.net/problem/17970

17970번: Islands

 

1. 정점의 순서들이 가지는 성질에 대해서 알아보자.

• 하나의 섬에서 $1$번째 정점부터 $i$번째 정점까지 하나의 구간을 이룬다.
• $i+1$번째 정점은 $1$번째 정점부터 $i$번째 정점이 이루는 구간과 인접해 있다.

시작점을 고정하자. 새로운 정점을 방문할 때마다 두 섬 모두에서 방문한 정점이 이루는 구간과 인접한 정점을 선택하는 그리디한 알고리즘이 성립한다. 따라서 문제를 시간복잡도 $O(N^2)$에 해결할 수 있다.

 

2. 정점 $i$와 섬 $j$에서 인접한 정점들의 집합을 $N_j(i)$로 정의하자. $N_1(i)=N_2(i)$를 만족하는 정점 $i$를 제거해도 모든 정점을 방문하는 경로의 존재 여부는 바뀌지 않는다.

$p$, $q$랑 인접한 정점 $r$이 있다고 가정하자. 시작점이 $r$인 경우에는 두 섬 모두에서 인접한 $p$, $q$를 방문하고 시작한다. 이는 $r$을 제거한 경우 $p$에서 시작해 $q$를 방문하는 경로와 동일하게 생각할 수 있다.

시작점이 $r$이 아닌 경우를 생각해보자. 편의상 $p$를 $q$보다 먼저 방문한다고 하자. $p$와 인접한 $r$, $r$과 인접한 $q$를 방문하게 된다. 이는 $r$을 제거한 경우 $p$에서 $q$를 방문하는 것과 동일하게 생각할 수 있다.

 

 

$N_1(i)=N_2(i)$를 만족하는 정점 $i$가 없을 때까지 계속해서 정점을 제거하자. 제거하다가 점의 개수가 $3$개가 된다면 아무 길이 3의 경로가 답이 될 수 있기 때문에 정점을 제거하기 전의 섬에서도 임의의 점에서 시작해서 답을 얻어낼 수 있다. 이제 모든 정점 $i$에 대해 $N_1(i) \neq N_2(i)$인 경우에 대해 알아보자.

 

3. 정점 $i$에서 시작한 탐색이 구간 $P_i$에서 끝난다고 하자. $P_i$ 밖의 정점 $j$에 대해 $P_j \neq \{1, 2, \cdots, N\}$이라면 $|P_i \cap P_j| \leq 2$이다.

$P_i \cap P_j$가 구간을 이루지 않고 $P_i$의 양쪽 끝에 존재한다고 하자. 그렇다면 $P_i^C \subset P_j$이다. $j$에서 시작해서 탐색을 할 때 $P_i$ 내부에 있는 정점의 우선순위를 가장 나중으로 한다면 방문한 정점들의 구간이 $P_i^C$가 되는 시점이 있다. $P_i^C$를 구성하는 경로와 $P_i$를 구성하는 경로의 끝점을 이어서 $j$에서 시작하는 길이 $N$의 경로를 완성할 수 있어서 모순이다.

따라서 $P_i \cap P_j$은 구간을 이룬다. $j$에서 교집합 내부의 정점을 구간의 시작에서 끝 순으로 탐색하기 때문에 $P_i \cap P_j$의 크기가 $3$ 이상이라면 $P_i \cap P_j$의 끝점이 아닌 점의 $N_1$과 $N_2$가 같아서 모순이다.

 

4. $j \in P_i$인 경우에 $P_j \subset P_i$이다. 위에서 설명한 그리디 알고리즘을 조금 더 보완하자. 시작점을 고정하고 그리디하게 탐색을 한 뒤에, 만약 길이 $N$의 경로를 만드는 데 실패했다면 탐색한 구간 내부에서 시작점을 잡지 않는 것이다.  이는 $O(N)$의 실행시간을 보인다. 

$P_i$의 끝부분에 있는 점을 2개씩 제거한 집합을 $Q_i$라고 하자. 위 알고리즘에서 시작점으로 잡은 정점은 $Q$가 겹치지 않는다. 따라서 길이 $N$의 경로가 나오기 전에 전체 탐색하는 정점의 개수는 $5N$개를 넘지 않는다.