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

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

2146번: 다리 만들기

 

문제접근 및 풀이

기본적으로 BFS로 접근했다.

 

2개의 섬만을 잇는 최단경로를 구해야 하므로 바다와 인접한 칸(테두리 칸이라고 하겠다)들을 구별했다.

그 후 테두리칸들에 대해 서로 bfs를 진행하면서 최단경로를 구하는 방식으로 해결했다.

 

step1 : 테두리 칸에 번호부여하기

- 부여받은 인풋배열 b[][]를 돌면서 각 섬에 대해 인덱싱(v[][])을 진행한다. 이때 바다와 인접하지 않은 지역은 -1로 설정해준다.

- 섬마다 테두리칸들을 구별해야 하므로 1,2,3,...이런식으로 증가하는 인덱스값을 부여해주었다.

 

step2 : 각 테두리 칸에 대해 BFS탐색하여 다른섬으로 가는 최단경로 탐색하기

- 테두리칸들에 대해 서로 bfs를 진행한다.

- 인덱싱한 값을 매게변수로 넘겨주어서 같은 섬의 테두리는 탐색하지 않도록 한다.

- 바다인 칸 혹은 다른 섬의 테두리만 탐색한다.

 

#include <iostream>
#include <queue>
#include <algorithm>
#define MAX 100 

using namespace std;

int n,key=1, result=987654321;
int b[MAX][MAX]={0};
int v[MAX][MAX]={0};
int k[MAX][MAX]={0};
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

void bfs(int i, int j, int key){
    queue<pair<int,int>> q;
    q.push({i,j});
    v[i][j]=1;
    while(!q.empty()){
        int find=0;
        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 && ny>=0&&nx<n&&ny<n){
                if(v[nx][ny]==0 && b[nx][ny]==1){
                    v[nx][ny]=1;
                    q.push({nx,ny});
                }
                if(b[nx][ny]==0){//b = 0 바다라면
                    k[x][y] = key;
                    find=1;
                }
            }
        }
        if(find==0){
            k[x][y]=-1;
        }
    }
    return ;
}

void bfs2(int i, int j, int key){
    //탐색조건 k[][] 가 -1(육지) 혹은 key(같은 테두리)가 아니라면 탐색
    int v[MAX][MAX]={0};
    queue<pair<pair<int,int>, int>> q;
    q.push({{i,j},0});
    v[i][j]=1;
    while(!q.empty()){
        int x = q.front().first.first;
        int y = q.front().first.second;
        int c = q.front().second;
        q.pop();
        if(k[x][y]!=0 && k[x][y]!=key){
            result = min(result, c);
            return ;
        }
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx>=0 && ny>=0&&nx<n&&ny<n){
                if(v[nx][ny]==0 && k[nx][ny]>=0 && k[nx][ny]!=key){ // 메모리초과 -> v체크안했었음
                    v[nx][ny] = 1;
                    q.push({{nx,ny}, c+1});
                }
            }
        }
    }
    return ;
}

int main()
{
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &b[i][j]);
        }
    }
    
    //step1 : 테두리 번호 부여하기 
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(b[i][j]==1 && v[i][j]==0){
                bfs(i,j,key);
                key++;
            }
        }
    }
    //step2 : 각 테두리 칸에 대해 bfs하여 다른 테두리 카능로 가는 최단거리 탐색 
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int key = k[i][j];
            if(key > 0){ // key가 0보다 크다면 번호가 부여된 테두리이다.
                bfs2(i,j,key);
            }
        }
    }
    
    cout << result-1;
    
    return 0;
}

 

느낀점

- 생각보다는 간단하게 해결되는 문제이지만 생각을 충분히 한 후에 단박에 풀어낼 수 있어서 뿌듯했다.