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

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

2146번: 다리 만들기

1. 영역 구하기

2. 영역 중에서 바다와 맞닿은 (= 제일 끝쪽에 있는) 곳들 찾아주는 함수 작성

3. 사이드 영역에서 다른 영역까지의 최단거리 구하기

이 문제의 해결법은 크게 위 3단계로 나눌 수 있다.

1번 해결법 설명 : dist배열을 활용하여 모든 육지가 아닌, 아직 탐색하지 않은 영역인 경우에만 탐색을 진행한다.

cnt 변수를 이용하여 번호를 매겨주면 된다!

2번 해결법 설명 : 바다와 맞닿아 있는 곳인지 판별하는 것은 쉽다! 4방향을 뒤졌는데 0인 곳을 만나면 참을 반환해주면 된다.

3번 해결법 설명 : 사이드 영역에서 다른 영역까지의 최단거리는 bfs를 활용하면 된다. 같은 번호의 육지인 경우에는 스킵해주고,

아직 방문하지 않은 바다를 만나거나 다른 영역을 만나면 큐에 넣고, 만약 해당 좌표가 육지이면서 다른 영역인 경우에는 최단거리를 갱신하며 bfs 탐색을 종료하면 된다. (bfs의 특성 상, 처음 만나는 곳이 시작 좌표로부터의 최단거리인 것을 이용했다.)

결국 마지막에 남은 ans 값이 최단거리의 다리 길이일 것이다!

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n,cnt,ans;
int board[101][101];
int dist[101][101];
bool visited[101][101];
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

void bfs(int a, int b){
    queue<pair<int,int>> q;
    dist[a][b]=cnt;
    q.push({a,b});

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        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 && dist[nx][ny]==-1 && board[nx][ny]==1){
                q.push({nx,ny});
                dist[nx][ny]=cnt;
            }
        }
    }
}

void bfs2(int a, int b) {
    queue<pair<pair<int, int>, int>> q;
    memset(visited, false, sizeof(visited));
    q.push({{a, b}, 0});
    visited[a][b] = true;

    int number = dist[a][b];

    while (!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int d = q.front().second;
        q.pop();

        if (dist[x][y] != number && board[x][y] == 1) {
            ans = min(ans, d - 1);
            return;
        }

        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) continue;

            if((dist[nx][ny]!=number || dist[nx][ny]==-1) && !visited[nx][ny]){
                q.push({{nx,ny}, d+1});
                visited[nx][ny] = true;
            }
        }
    }
}

bool side(int a, int b){
    for(int i=0; i<4;i++){
        int nx = a + dx[i];
        int ny = b + dy[i];

        if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;

        if(board[nx][ny]==0){
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n;

    memset(dist, -1, sizeof(dist));

    cnt=1;
    for(int i=0; i<n;i++){
        for(int j=0; j<n;j++){
            cin >> board[i][j];
        }
    }

    for(int i=0; i<n;i++){
        for(int j=0; j<n;j++){
            if(board[i][j] == 1 && dist[i][j]==-1){
                bfs(i,j);
                cnt++;
            }
        }
    }

    ans = 987654321;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(board[i][j]==1 && side(i,j)){
                bfs2(i,j);
            }
        }
    }
    cout << ans << "\n";

    return 0;
}