[BOJ] C++ 2146 다리 만들기 - 방문 조건이 굉장히 헷갈리는 BFS

2146번: 다리 만들기

예제

10
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0

ans : 3

---

먼저 bfs를 통해 섬에 번호를 매겨줄 필요성을 느꼈다. 어떤 풀이를 쓰던 무조건 섬끼리 구분이 되어야 하기 때문이다. 구현은 어려운 부분은 없고 가장 기본적인 bfs로 구현해 주면 된다.

void numbering_island(int x, int y)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(x, y));
    island[x][y] = island_number;
    while (!Q.empty())
    {
        auto cur = Q.front();
        Q.pop();

        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            if (!(nx >= 0 && ny >= 0 && nx < n && ny < n))
                continue;
            if (island[nx][ny] != 0)
                continue;
            if (arr[nx][ny] == 0)
                continue;
            island[nx][ny] = island_number;
            Q.push(make_pair(nx, ny));
        }
    }
}

섬을 넘버링 해준 후가 문제인데, bfs로 최단 거리를 구하면 될 것 같았다. 그런데 방문 조건이 굉장히 헷갈렸다. 방문 조건을 정리해보자. 가장 처음에 생각한 것은 섬 별로 아무거나 하나를 대표로 넣어서 bfs를 돌리는 것이었다.

 

1. 같은 섬이면 그 섬의 dist를 0으로 하고 continue;

2. 다른 섬이면 return dist;

3. 바다를 만나면 해당 바다를 방문처리 하고 dist+1로 저장.

 

위의 방식을 먼저 떠올렸는데 정말 많은 오류가 있었다. 예를 들면, 1 0 1 같은 경우(1은 모두 같은 섬이다.) 같은 섬이지만 바다를 만나면서 어느 섬에서 출발한 bfs인지 저장할 수 없었다. 그리고 섬의 개수가 많아지면 처음 의도한 대로 작동이 전혀 되지 않았고 그래서 생각한 풀이가 일단 모든 섬을 넣자였다. 모든 섬을 넣으니 갈피가 좀 잡혔다.

 

1. 같은 섬이면 continue;

2. 바다를 만나면 바다를 현재 방문하고 있는 섬과 같은 영역으로 바꾸고 dist를 기록한다.

3. 다른 섬을 만나는 경우에는 만나는 부분이 사실은 원래 바다였을 가능성이 높다. 바다를 섬처럼 기록하면서 어찌보면 실시간으로 다리를 만들면서 진행하였기에 만나는 부분의 dist를 서로 더해주면 다리를 구할 수 있다. 그런데 가장 먼저 구한 답이 최종 최단 거리가 아닐 수 있다. 모든 섬에서 동시에 시작한 bfs기에 다른 섬과 만나면 그 섬은 push 하지 않고 큐가 빌 때까지 지켜보아야 한다.

 

생각한 알고리즘 그대로 구현하면 된다.

/** BFS 2146 다리 만들기 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;

const int MAX = 102;
int arr[MAX][MAX];
int island[MAX][MAX];
int dist[MAX][MAX];
int island_number = 1;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int n;
int res = 999999;

void numbering_island(int x, int y)
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(x, y));
    island[x][y] = island_number;
    while (!Q.empty())
    {
        auto cur = Q.front();
        Q.pop();

        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            if (!(nx >= 0 && ny >= 0 && nx < n && ny < n))
                continue;
            if (island[nx][ny] != 0)
                continue;
            if (arr[nx][ny] == 0)
                continue;
            island[nx][ny] = island_number;
            Q.push(make_pair(nx, ny));
        }
    }
}

void bfs()
{
    queue<pair<int, int>> Q;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (island[i][j] != 0)
            {
                Q.push(make_pair(i, j));
                dist[i][j] = 0;
            }
        }
    }
    while (!Q.empty())
    {
        auto cur = Q.front();
        Q.pop();

        for (int dir = 0; dir < 4; dir++)
        {
            int nx = cur.first + dx[dir];
            int ny = cur.second + dy[dir];
            if (!(nx >= 0 && ny >= 0 && nx < n && ny < n))
                continue;
            if (island[nx][ny] == island[cur.first][cur.second])
                continue;
            if (island[nx][ny] != 0)
            {
                // 섬 만나면 다리 길이 구하기
                res = min(res, dist[cur.first][cur.second] + dist[nx][ny]);
            }
            else
            {
                // 바다 만나는 경우 해당 바다를 섬과 같은 영역으로 만들어 줘야 한다.
                // 1 0 1 과 같은 예시에서 꼬일 수 있다.
                island[nx][ny] = island[cur.first][cur.second];
                dist[nx][ny] = dist[cur.first][cur.second] + 1;
                Q.push(make_pair(nx, ny));
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> arr[i][j];
            island[i][j] = 0;
            dist[i][j] = -1;
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (arr[i][j] != 0 && island[i][j] == 0)
            {
                numbering_island(i, j);
                island_number++;
            }
        }
    }

    bfs();

    cout << res;
}