[boj] 백준 2146 다리 만들기 (c++) - BFS

[문제]

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

2146번: 다리 만들기

 

[풀이]

bfs 문제.

 

고려해주어야 할 사항은 크게 다음 2가지이다.

 

1. 서로 같은 섬끼리 묶어준다. 한 육지에서 바다를 건너 다른 육지로 이동했다 해도 같은 섬이라면 다리를 놓는 것이 성립이 안되기 때문이다. 처음 육지를 -1로 변환해서 저장해주고 bfs 를 통해 1, 2, 3..으로 라벨링해준다.

 

2. bfs로 섬 사이에 다리를 놓는다. 라벨링된 섬 별로 섬들을 모두 queue에 넣어주고 다른 섬에 도착했을 때의 다리 길이를 return해 준다.  방문하지 않은 바다라면 다리 길이를 1 더해서 queue에 넣는다.

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <math.h>
#define INF 987654321

using namespace std;

int n;
int island[101][101];
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
bool visited[101][101];

struct bridge{
    int r, c;
    int length;
};

void label_bfs(int r, int c, int label){
    queue<pair<int, int>> q;

    q.push({r, c});
    visited[r][c] = true;
    island[r][c] = label;

    while(!q.empty()){
        int r = q.front().first;
        int c = q.front().second;
        q.pop();

        for(int i=0; i<4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];

            if(nr<0 || nc<0 || nr>=n || nc>=n) continue;

            if(!visited[nr][nc] && island[nr][nc]==-1){
                island[nr][nc] = label;
                visited[nr][nc] = true;
                q.push({nr, nc});
            }
        }
    }
}

int bfs(int idx){
    queue<bridge> q;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(island[i][j]==idx){
                visited[i][j] = true;
                q.push({i, j, 0});
            }
        }
    }

    while(!q.empty()){
        int r = q.front().r;
        int c = q.front().c;
        int len = q.front().length;
        q.pop();

        for(int i=0; i<4; i++){
            int nr = r + dr[i];
            int nc = c + dc[i];

            if(nr<0 || nc<0 || nr>=n || nc>=n) continue;

            //다른 섬에 도달한 경우
            if(island[nr][nc]!=0 && island[nr][nc] != idx){
                return len;
            }

            //바다이면서 방문하지 않은 경우
            if(island[nr][nc]==0 && !visited[nr][nc]){
                visited[nr][nc] = true;
                q.push({nr, nc, len+1});
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> island[i][j];
            if(island[i][j]!=0)
                island[i][j] = -1;
        }
    }

    int label = 1;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(island[i][j]==-1 && !visited[i][j]){
                label_bfs(i, j, label++);
            }
        }
    }

    int ans = 987654321;
    for(int i=1; i<label; i++){
        memset(visited, false, sizeof(visited));
        ans = min(ans, bfs(i));
    }

    cout << ans;
}