[백준 2146번] 다리 만들기

문제 링크:https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

<문제 풀이> BFS

섬의 육지에서 시작해서 BFS로 다른 섬의 육지에 최초로 만나는 지점이 다리를 놓을 수 있는 방법 중에 하나입니다.

그래서 문제를 해결하기 위해서

1. bfs로 섬을 구분한다. 

10
1 1 1 0 0 0 0 2 2 2
1 1 1 1 0 0 0 0 2 2
1 0 1 1 0 0 0 0 2 2
0 0 1 1 1 0 0 0 0 2
0 0 0 1 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
0 0 0 0 3 3 0 0 0 0
0 0 0 0 3 3 3 0 0 0
0 0 0 0 0 0 0 0 0 0

2. i번째 섬의 모든 육지를 큐에 담고 최초로 다른 섬과 만날 때까지 최단거리를 갱신한다.

-> 모든 섬에 대해서 bfs를 돌리고 최솟값을 구하면 됩니다. 

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
#define X first
#define Y second
 
int board[100][100];
int visited1[100][100]; // 섬 구분
int visited2[100][100]; // 최단 거리
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1 , 0, -1, 0 };
 
int n;
int flag = 1;
int res = INT_MAX;
 
void bfs1() {// 섬 구분
    queue<pair<int, int> > Q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 1 && !visited1[i][j]) {
                Q.push({ i, j });
                visited1[i][j] = true;
                board[i][j] = flag;
                while (!Q.empty()) {
                    auto cur = Q.front(); Q.pop();
                    for (int dir = 0; dir < 4; dir++) {
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
                        if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
                        if (board[nx][ny] != 1 || visited1[nx][ny])continue;
                        Q.push({ nx, ny });
                        board[nx][ny] = flag;
                        visited1[nx][ny] = true;
                    }
                }
                flag++;
            }
        }
    }
    flag--;
}
 
void bfs2() { //최단거리
    flag = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == flag) {
                queue<pair<int, int> > Q;
                Q.push({ i, j });
                visited2[i][j] = 1;
                while (!Q.empty()) {
                    auto cur = Q.front(); Q.pop();
                    for (int dir = 0; dir < 4; dir++) {
                        int nx = cur.X + dx[dir];
                        int ny = cur.Y + dy[dir];
                        if (nx < 0 || ny < 0 || nx >= n || ny >= n)continue;
                        if (visited2[nx][ny] && visited2[nx][ny] <= visited2[cur.X][cur.Y] + 1)continue;
                        if (board[nx][ny] == flag) {
                            visited2[nx][ny] = 1;
                            Q.push({ nx, ny });
                        }
                        else if (board[nx][ny] == 0) {
                            visited2[nx][ny] = visited2[cur.X][cur.Y] + 1;
                            Q.push({ nx, ny });
 
                        }
                        else if (board[nx][ny] != flag) {
                            res = min(res, visited2[cur.X][cur.Y] - 1);
                          
                        }
                    }
                }
                flag++;
                fill(&visited2[0][0], &visited2[99][100], 0);
            }
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }
    bfs1();
    bfs2();
    cout << res;
    return 0;
}