대회풀이

보도블록이 2x2 이상일 때 항상 모든 블록을 방문할 수 있다. 주어진 보도블록을 작은 보 도블록들로 쪼갠 뒤, 재귀적으로 작은 보도블록들에 대한 경로들을 다시 연결하는 분할정복 (Divide-And-Conquer) 알고리즘으로 쉽게 해결할 수 있다. 별다른 탐색 과정 없이 바로 해 를 구할 수 있으므로 시간복잡도는 O(MN)이 된다. 다양한 해가 존재하므로 자신만의 규칙 을 찾아 구현하면 된다.

그 중 이해하기 쉬운 방법 하나를 아래에 소개한다.

(가) 2행 N열

직사각형(ㅁ) 모양으로 순서대로 방문하면 된다.

(나) 짝수행 N열

행의 수가 짝수개일 경우 2행 단위로 나누어 (1)을 적용하면 된다. 예를 들어 8행 7열 보도 블록의 해는 2행 7열의 해 4개를 역 디귿자(ㄷ)가 반복되게 아래로 이어 붙이면 된다. 그림 에는 생략되었지만 회색 블록과 흰색 블록의 방문 순서도 고려해야 한다.

(다) 3행 N열

열의 수가 짝수인 경우와 홀수인 경우를 나누어 규칙을 찾을 수 있다. 마찬가지로 회색 블 록과 흰색 블록의 방문 순서에도 고려하도록 한다.

(5) 비용 (COST)

정의상 Cost를 구할 때는 작은 에지부터 끊어가면서 구하지만 실제 풀이는 반대로 아무 에지도 없는 상태에서 가장 가중치가 큰 에지를 붙여가며 생각한다. 어떤 에지를 붙일 때, 새로 연결이 되는 정점의 그룹은 그 에지가 끊어지는 순간에 연결이 끊어지는 그룹들이다. 그러한 이유로 에지를 이어가며 각 순간에 새롭게 이어지는 정점 쌍의 개수에 에지 가중치 합을 곱해주며 그 값을 다 더해주면 된다. 정점 그룹에 대한 처리를 Union Find에 해주면 상수시간에 가까운 시간으로 서로소인 그룹(Disjoint Group)을 처리할 수 있다. 시간복잡도 O(N+MlogM)에 해결 가능하다.