[C++/백준] 2146번: 다리 만들기

문제 링크

2146번: 다리 만들기

 

풀이

BFS 문제

1. 섬에 대해서 BFS를 돌리면서 섬의 종류를 나눠준다.
2. 육지에 대해 바다 옆에 있는 육지라면 q에 해당 육지를 넣어주고, 해당 거리부터 시작하기 위해 dist 값은 0으로 넣어준다.
3. 다리를 짓기 위해 BFS를 돌릴건데, 해당 다리가 어느 섬에서부터 지어진건지 체크하며(island), 같은 섬에서 지어진 다리라면 continue, 다른 섬에서 지어진 다리라면 그 두 개의 다리를 이어주면 된다. (dist[ny][nx] + dist[ty][tx])
4. 3번의 경우의 수가 다 아닐 경우 바다이기 때문에 dist와 island를 갱신해주고 q에 넣어준다.
5. 3번에서 두 개의 다리를 이어준 것 중 최솟값을 출력한다.

 

코드

#include <iostream>
#include <queue>
#include <tuple>
#define INF 10005
using namespace std;

int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };

int n;
int arr[101][101];
int island[101][101]; // 육지 나누기
int dist[101][101]; // 다리가 지어질 때 거리

int main()
{
    ios::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];
            dist[i][j] = INF;
            island[i][j] = INF;
        }
    }

    int cur = 1; // 육지를 나눌 변수
    for (int i = 0; i < n; i++) // 섬을 나눠주는 BFS
    {
        for (int j = 0; j < n; j++)
        {
            if (arr[i][j] == 1 && island[i][j] == INF)
            {
                queue<pair<int, int>> q;
                island[i][j] = cur;
                q.push({ i,j });

                while (!q.empty())
                {
                    int ty = q.front().first;
                    int tx = q.front().second;
                    q.pop();
                    for (int d = 0; d < 4; d++)
                    {
                        int ny = ty + dy[d];
                        int nx = tx + dx[d];
                        if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
                        if (island[ny][nx] != INF) continue;
                        if (arr[ny][nx] == 1)
                        {
                            island[ny][nx] = cur;
                            q.push({ ny,nx });
                        }
                    }
                }

                cur++;
            }
        }
    }

    queue<pair<int, int>> q;
    for (int i = 0; i < n; i++) // 육지 옆에 바다 인 경우 해당 육지를 q에 넣어주기
    {
        for (int j = 0; j < n; j++)
        {
            for (int d = 0; d < 4; d++)
            {
                int ny = i + dy[d];
                int nx = j + dx[d];
                if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
                if (dist[ny][nx] != INF) continue;
                if (island[i][j] != INF && arr[ny][nx] == 0)
                {
                    q.push({ i, j });
                    dist[i][j] = 0;
                }
            }
        }
    }

    int ans = INF;
    while (!q.empty())
    {
        int ty, tx;
        tie(ty, tx) = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = ty + dy[i];
            int nx = tx + dx[i];
            if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
            if (island[ny][nx] == island[ty][tx]) continue; // 인접한 섬이 같은 섬일 경우
            if (island[ny][nx] != INF) // 인접한 섬이 다른 섬일 경우
            {
                ans = min(ans, dist[ny][nx] + dist[ty][tx]);
            }
            else
            {
                island[ny][nx] = island[ty][tx];
                q.push({ ny,nx });
                dist[ny][nx] = dist[ty][tx] + 1;
            }
        }
    }
    cout << ans;
}