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

2146번: 다리 만들기

---

풀이

bfs가 아닌 dfs로 풀어서 조금 애먹었던 문제이다.

섬들에 번호를 매기고 각 섬의 가장자리 부분들의 위치를 저장한뒤 가장자리 에서 부터 시작해서 다른 섬으로 다리를 점점 넓혀나가면 된다.

 

코드

#include <bits/stdc++.h>

using namespace std;

int board[101][101];
int flag[101][101];
int region[101][101];

int regionNum = 1;
int n;

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

vector<pair<int,int>> edges;
int mminL = 1000000;
bool InMap(int x, int y){
    if(0 <= x && x < n && 0 <= y && y < n)
    return true;
    return false;
}

void FindRegion(int x,int y){
    if(region[y][x] != 0){
        return;
    }
    region[y][x] = regionNum;
    int nR = region[y][x];
    
    bool isEdge = false;
    for(int i =0; i < 4; i++){
        int nx = dx[i] + x;
        int ny = dy[i] + y;
        if(InMap(nx,ny) && board[ny][nx] == 1 && region[ny][nx] == 0){
            FindRegion(nx,ny);
        }
        if(InMap(nx,ny) && board[ny][nx] == 0){
            isEdge = true;
        }
    }
    
    if(isEdge){
        edges.push_back(make_pair(x,y));
    }
}
int BuildBridge(int x,int y){
    int minL = 100000;
    int r = region[y][x];
    queue<tuple<int,int,int>> nextQ;
    nextQ.push(make_tuple(x,y,0));
    
    while(!nextQ.empty()){
        int qx = get<0>(nextQ.front());
        int qy = get<1>(nextQ.front());
        int ql = get<2>(nextQ.front());
        nextQ.pop();
        if(flag[qy][qx] <= ql){
            continue;
        }
        flag[qy][qx] = ql;
        for(int i =0; i < 4; i++){
        int nx = dx[i] + qx;
        int ny = dy[i] + qy;
        if(!InMap(nx,ny)){
            continue;
        }
        
        if(board[ny][nx] == 0 && flag[ny][nx] > ql+1){
            nextQ.push(make_tuple(nx,ny,ql+1));
        }
        if(board[ny][nx] == 1 && region[ny][nx] != r){
            minL = min(minL, ql);
        }
        }
    }
    if(mminL <= minL){
        minL = mminL;
    }
    flag[y][x] = minL;
    return minL;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
     
    for(int y = 0; y < n; y++){
        for(int x = 0; x < n; x++){
           cin >> board[y][x]; 
        }
    }
    for(int y = 0; y < n; y++){
        for(int x = 0; x < n; x++){
            flag[y][x] = 100000;
           if(board[y][x] == 1 && region[y][x] == 0){
               FindRegion(x,y);
               regionNum++;
           }
        }
    }

    for(int i =0; i < edges.size(); i++){
        int x = edges[i].first;
        int y = edges[i].second;
        mminL = min(mminL,BuildBridge(x,y));
    }
    cout << mminL;
    return 0;
}