BOJ 2146:: 다리 만들기

http://acmicpc.net/problem/2146

문제에 따르면 다리는 서로 다른 섬의 두 해안가 지역 사이에 세워야 합니다. 풀이 방향을 대충 세워보면

  1. DFS/BFS를 이용해 섬을 구분한다. (문제에서는 섬을 구분하지 않고 무조건 1로 주어지니, 이걸 섬마다 다른 수로 바꿔줍시다)
  2. 각 지점마다 해안가인지 판별한다. (인접한 4칸 중에 바다가 있는지)
  3. 서로 다른 섬의 해안가 지역 두 곳을 골랐을 때 이들 사이를 잇는 데 필요한 다리 길이의 최솟값을 구한다.

1번과 2번은 쉽습니다. 3번이 관건인데, 일단 다리 길이가 최소가 되는 해안가 지역 두 곳을 이미 알고 있다고 해봅시다. 예컨데 주어진 예제 입력에서는 아래와 같습니다.

저 두 점을 서로 마주보는 꼭짓점으로 하는 사각형을 생각해봅시다. 그럼 그 사각형 안에는 육지가 저 두 점만 있어야 합니다. 증명은 귀류법으로 합니다. 만약 사각형 안에 다른 육지가 또 포함되어 있다고 해봅시다.

보시다시피 당연히 빨간 점과 초록 점 사이에 다리를 놓는 것보다 빨간 점과 그 중간에 있는 다른 육지 사이에 다리를 놓는 게 훨씬 짧습니다. 빨간 점과 초록 점을 잇는 것보다 더 짧게 다리를 건설하지 못한다고 가정했으므로 모순입니다.

이게 무엇을 의미하냐면, 다리 길이가 최소가 되는 두 점 사이에 다리를 놓을 때 맨해튼 거리로 이어버릴 수 있다는 겁니다. 육지 때문에 빙글빙글 돌아가야 하는 일은 일어나지 않습니다. 정확히는 (두 점 사이의 맨해튼 거리) – 1이죠.
따라서 풀이 방법을 다시, 그리고 조금 더 자세히 적어봅시다. 먼저 최솟값을 저장할 변수(best라고 합시다)를 만들고 적당히 큰 수로 초기화해줍니다.

  1. DFS/BFS를 이용해 섬을 구분한다. (문제에서는 섬을 구분하지 않고 무조건 1로 주어지니, 이걸 섬마다 다른 수로 바꿔줍시다)
  2. 각 지점마다 해안가인지 판별한다. (인접한 4칸 중에 바다가 있는지)
  3. 모든 점을 2중 for문으로 돌면서, 만약 해안가에 해당하는 점이면 다시 2중 for문을 돌면서
    1. 같은 섬에 속하지 않는 해안가 점인지 확인한다.
    2. 해당하는 경우 (두 점 사이의 맨해튼 거리) – 1을 구하고 그 값이 best보다 작으면 best를 그 값으로 바꾼다.

답이 나오는 해법이긴 하나, for문 중첩에 의해 시간이 꽤 낭비됩니다. 가장 시간 낭비가 심한 부분은 3번에서 해안가 점에 대해 또 2중 for문을 도는 부분입니다. 바깥쪽 2중 for문이 $n^2$이고 안쪽도 $n^2$이니 해안가 점이 몇 개냐에 따라 다르겠습니다만 최악의 경우 $n^4$정도로 생각할 수 있겠습니다. 그래서 안쪽 for문을 어떻게 최적화하냐면, 위에서 굳이 언급한 best를 사용합니다.


바깥쪽 for문이 빨간 화살표를 따라 순회하여 현재 빨간 점에 방문하려 합니다. 이 때 best의 값은 (직접 구해보면 아시겠지만) 4입니다. 빨간 점은 해안가에 해당하므로, 안쪽 for문을 순회하게 될텐데, 중요한 건 어차피 맨해튼 거리가 4(현재 best 값)보다 큰 다른 섬의 해안가 점을 방문해봤자 그 점까지 (맨해튼 거리) – 1은 4 이상이니 best가 안 바뀐다는 겁니다. 그러니 안쪽 for문에서는 굵은 선으로 표시한 영역 내에 있는 점들만 순회해보면 된다는 겁니다! (마름모 위쪽이 잘린 이유는 똑같은 점 쌍을 중복으로, 두 번 계산하지 않기 위해) 저 영역 안에 해안가는 두 개 있고, 그 중 노란색은 같은 섬이니까 패스. 초록색은 다른 섬이니까 (맨해튼 거리) – 1을 하면 3이 나오고 따라서 best가 3으로 업데이트 됩니다. 그러면 빨간 점의 방문이 끝났고, 이후부터는 best가 3인채로 순회할테니 저 마름모의 크기가 한 칸 줄어든 상태가 되겠죠.

… 그런데 저 마름모 모양으로 순회하도록 코드를 짜는 게 상당히 귀찮은 관계로, 그냥 아래와 같이 단순화했습니다 …

(직사각형의 장점은 생각없이 2중 for문을 짤 수 있다는 겁니다)