Up

BOJ 2146:: 다리 만들기

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

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

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

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

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

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

  1. DFS/BFS를 이용해 섬을 구분한다.
  2. 각 지점마다 해안가인지 판별한다.
  3. 모든 해안가 지점의 쌍에 대해 (둘 사이의 맨해튼 거리 - 1)을 구한다.
  4. 최종 정답은 3에서 구한 값 중 최솟값이다.