[BFS, 난이도 중상] 백준 2146번 다리 만들기

본인은 두 Step으로 나눠서 문제를 해결하였다.

큐는 각각 q,q2 이라는 이름의 큐 총 2개를 사용하였다.

 

Step1에서는 q를 이용해 아래 그림과 같이 나라별로 숫자로 분류하였다.

Step2에서 BFS를 수행하면서 어떤 나라를 만났을 때, 그게 자신의 나라인지 남의 나라인지 구별하는 과정을 거칠 것이기 때문이다. 이 과정 때문에 개인적으로 이 문제의 난이도는 중상으로 평가한다.

 

Step2에서는 q2로 모든 지도를 탐색하여 방문하지 않은 바다 좌표를 만날 때마다 큐에 넣고, 방문 처리를 한다.

만약 탐색한 나라가 출발한 나라와 다를 경우, 구조체 node 에서 다리의 길이를 의미하는 depth 를 found 변수에 넣고

최솟값을 업데이트 해나갔다. 

 

<구조체 설명>

g -> 나라 번호

depth -> 다리 깊이

x,y -> 지역 좌표

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;

struct node{
    int g,depth,x,y;
};

int map[101][101];
bool visited[101][101];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int n;

int mini(int a,int b){
    if(a<b)return a;
    else return b;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    int ans=10001;
    queue<pair<int,int> > q;
    
	for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin >> map[i][j];
        }
    }
    
    int group=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!visited[i][j]&&map[i][j]!=0){
                q.push(make_pair(i,j));
                visited[i][j]=true;
                map[i][j]=group;
                while(!q.empty()){
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();
                    for(int k=0;k<4;k++){
                        if(x+dx[k]<0 || y+dy[k]<0 || x+dx[k]>=n || y+dy[k]>=n) continue;
                        if(!visited[x+dx[k]][y+dy[k]]&&map[x+dx[k]][y+dy[k]]!=0){
                            q.push(make_pair(x+dx[k],y+dy[k]));
                            visited[x+dx[k]][y+dy[k]]=true;
                            map[x+dx[k]][y+dy[k]]=group;
                        } 
                    }
                }
                group++;
            }
        }
    }
    
    memset(visited,false,sizeof(visited));
    queue<node> q2;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int found=0;
            if(map[i][j]>0){
                q2.push(node{map[i][j],0,i,j});
                while(!q2.empty()){
                    node f=q2.front();
                    q2.pop();
                    for(int k=0;k<4;k++){
                        if(f.x+dx[k]<0 || f.y+dy[k]<0 || f.x+dx[k]>=n || f.y+dy[k]>=n) continue;
                        if(map[f.x+dx[k]][f.y+dy[k]]!=f.g && map[f.x+dx[k]][f.y+dy[k]]>0){
                            found=f.depth;
                            break;
                        }
                        if(!visited[f.x+dx[k]][f.y+dy[k]]&&map[f.x+dx[k]][f.y+dy[k]]==0){
                            q2.push(node{map[i][j],f.depth+1,f.x+dx[k],f.y+dy[k]});
                            visited[f.x+dx[k]][f.y+dy[k]]=true;
                        } 
                    }
                    if(found){
                        ans=mini(ans,found);
                        while(!q2.empty()){
                            q2.pop();
                        }
                        memset(visited,false,sizeof(visited));
                    }
                }
            }
        }
    }
    if(ans==10001) ans=0;
    cout << ans;
}