백준 2146 다리 만들기 C++

https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

 이번 문제는 1, 0으로 이루어진 2차원 배열이 주어지고, 1로 구성된 섬을 잇는 가장 짧은 다리의 길이를 구하는 문제이다. 이 때, 다리는 상, 하, 좌, 우 방향으로만 연결될 수 있다. 그리고 각 섬들이 바다와 이어지는 부분에서 다리를 지을 수 있다. 그렇기 때문에, 이는 너비 우선 탐색 방법을 이용하여 푸는 것이 좋다고 생각한다. 이를 이용해 구현한 방법은 다음과 같다.

1. 2차원 배열의 행, 열 길이와 2차원 배열을 입력 받는다.
2. 각 섬들을 찾아야 한다. 우선, 2차원 배열을 하나 하나 검사한다.
   1. 만약 2차원 배열에서 배열[r][c]의 값이 0 이상이며 체크를 하지 않은 곳이라면 그 칸에 섬의 번호를 달아주고 탐색을 한다.
   2. 해당 좌표를 기준으로 상, 하, 좌, 우의 칸의 값이 0 이상이며 체크를 하지 않은 곳인지 확인한다. 만약 그렇다면, 그 곳도 섬 번호를 매겨준 후 탐색한다. 그리고 탐색하는 곳의 상, 하, 좌, 우 중 하나라도 0인 곳(바다)이 있다면 그 곳은 다리를 설치할 수 있는 곳이므로 따로 저장한다.
3. 모든 섬에 대한 탐색이 끝났다면 위에서 저장해 둔 다리를 설치할 수 있는 곳들을 체크한다.
   1. 위와 마찬가지로 상, 하, 좌, 우를 탐색하는데, 이 때는 다리를 짓는 순서이므로 각 좌표의 값이 0이어야 한다. 그 곳의 값이 0이며 체크하지 않은 곳이라면 큐를 이용해 그 곳도 탐색한다.
   2. 만약 다음 좌표의 값이 0이 아니고 현재 다리를 놓기 시작한 섬도 아니라면, 현재 다리의 길이가 가장 짧은 다리인지 체크한다. 

이를 구현한 코드는 아래와 같다.