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

📌문제 링크

---

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

📌문제 설명

---

먼저, 입력받은 지도에서 DFS를 사용하여 각 섬을 구분하고 고유 ID를 할당합니다. 이후, 각 섬의 경계에 해당하는 지점을 BFS 큐에 추가하고, BFS를 통해 바다를 건너며 다른 섬과의 최단 거리를 계산합니다. 두 섬이 만나면 다리 길이를 업데이트하며 최소값을 구합니다. 최종적으로 가장 짧은 다리 길이를 출력합니다.

📌코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

int N, mp[101][101], check[101][101], dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
queue<pair<int, int>> q;

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> mp[i][j];
            check[i][j] = 0;
        }
    }
}

void dfs(int x, int y, int id) {
    check[x][y] = id;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < N && ny >= 0 && ny < N && mp[nx][ny] == 1 && check[nx][ny] == 0) {
            dfs(nx, ny, id);
        }
    }
}

int bfs() {
    int answer = INT_MAX;

    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                if (mp[nx][ny] == 0 && check[nx][ny] == 0) {
                    check[nx][ny] = check[x][y];
                    mp[nx][ny] = mp[x][y] + 1;
                    q.push({nx, ny});
                } else if (mp[nx][ny] > 0 && check[nx][ny] != check[x][y]) {
                    answer = min(answer, mp[x][y] + mp[nx][ny] - 2);
                }
            }
        }
    }
    return answer;
}

void solve() {
    int id = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (mp[i][j] == 1 && check[i][j] == 0) {
                dfs(i, j, id++);
            }
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (mp[i][j] == 1) {
                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (nx >= 0 && nx < N && ny >= 0 && ny < N && mp[nx][ny] == 0) {
                        q.push({i, j});
                        break;
                    }
                }
            }
        }
    }

    cout << bfs() << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    input();
    solve();
    return 0;
}