백준 2146번 - 다리 만들기

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

위의 문제는 DFS를 이용하여 섬을 구분한 뒤에

섬에 있는 육지와 다른 섬의 육지 까지의 거리를 모두 구해서 최단 거리를 구하면 되는 문제이다.

각각의 섬들을 구분하여 저장하기 위해 나는 큐를 이용하였다.

육지가 이어져있는 하나의 섬을 찾았을 때 이 섬을 1이라고 한다면

다른 섬들은 2, 3과 같이 섬의 번호를 구별하여 큐에 저장할 수 있도록 했다.

즉 하나의 큐에는 구조체를 이용해 다음과 같은 값을 저장할 수 있도록 했다.

y좌표 / x좌표 / 섬의 번호

큐에 저장된 모든 좌표는 육지이기 때문에

육지 사이의 거리를 구할 수 있게 되는데

이때, 섬의 번호가 같다면 거리값을 구하지 않도록 하면 된다.

마지막으로 육지 사이의 거리는 두 육지의 y좌표와 x좌표끼리의 값을 뺀 후에 1을 빼주면 된다.

문제를 해결하는 과정을 요약하면 다음과 같다.

1)DFS를 이용해 섬을 하나씩 찾는다

2)DFS를 돌리는 과정에서 바다가 아닌 육지의 위치를 큐에 저장한다.

3)while문을 이용해 큐에 저장된 모든 육지 사이의 거리를 구한다

   (두개의 육지가 같은 섬에 해당한다면 패스)

#include <iostream>
#include <queue>
using namespace std;
 
int N;
 
int map[100][100]={0};
 
int visited[100][100]={0};
int dy[4]={1,-1,0,0};
int dx[4]={0,0,1,-1};
 
struct str{
    int y,x,cnt;
    str(int y,int x,int cnt):y(y),x(x),cnt(cnt){};
};
 
queue<str> q;
void dfs(int y,int x,int cnt){
 
    for(int i=0;i<4;i++){
        int ny=y+dy[i];
        int nx=x+dx[i];
        
        if(ny<0 || ny>=N || nx<0 || nx>=N)
            continue;
        
        if(map[ny][nx]==0 || visited[ny][nx])
            continue;
        
        visited[ny][nx]=1;
        q.push(str(ny,nx,cnt));
        
        dfs(ny,nx,cnt);
    }
    
}
 
int main(){
    
    scanf("%d",&N);
    
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            scanf("%d",&map[i][j]);
    
    
    int cnt=0; //섬 번호
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j]&&!visited[i][j]){
                
                visited[i][j]=1;
                q.push(str(i,j,++cnt));
                dfs(i,j,cnt);
            }
        }
    }
    
    int ans=1000; //가장 짧은 다리 길이
    int length=0; //두 섬 사이의 다리 길이
    
    while(!q.empty()){
        int y=q.front().y;
        int x=q.front().x;
        int cnt=q.front().cnt;
        
        q.pop();
        queue<str> q2=q;
        while(!q2.empty()){
            int y2=q2.front().y;
            int x2=q2.front().x;
            int cnt2=q2.front().cnt;
            
            q2.pop();
            
            if(cnt2==cnt)
                continue;
            
            length=abs(y2-y)+abs(x2-x)-1;
            ans=min(ans,length);
        }
    }
    
    cout<<ans<<endl;
    return 0;
}