[백준] 2146번. 다리 만들기

[문제]

 

www.acmicpc.net/problem/2146

2146번: 다리 만들기

[풀이]

 

섬을 연결하는 다리를 설치할 수 있는데, 가장 짧은 다리 하나를 설치할 수 있다.

이 때 가장 짧은 다리의 길이를 구하는 문제.

 

처음에는 섬을 분리하여, 섬의 가장자리에서 다른 섬의 가장자리로의 최단 거리를 구하려고 했다.

생각해보니 가장자리를 따로 구하지 않고 ,

BFS를 통해 최단 거리를 구하면 하나의 섬의 가장자리에서 다른 섬의 가장자리까지의 거리가 된다. 

 

따라서 DFS 함수에서 각 섬을 구분하고, BFS 함수에서 섬 간의 최단거리를 구했다.

BFS에서 최단거리를 구할 때 시작섬의 좌표를 queue에 모두 넣어줬다.

그리고 하나씩 pop하여 상,하,좌,우 방향으로 퍼져나갔다.

이 때 다른 섬을 만나면 거리를 return 하면서 BFS 함수를 종료하였다. 

 

이와 같은 방식으로 첫번째 섬부터 마지막 섬까지 반복하여  가장 짧은 다리의 길이를 구할 수 있다. 

 

[코드]

 

시간 : 44ms

 

#include <iostream>
#include <queue>
#define MAX 101

using namespace std;

struct pos{
    int x,y;
};

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int map[MAX][MAX]={0,};
bool tmp[MAX][MAX]={0,};
int N;
int cnt=0;
int answer=MAX*MAX;

void DFS(int x, int y,int cnt)
{
    map[x][y]=cnt;
    tmp[x][y]=true;
    
    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 || tmp[nx][ny] || map[nx][ny]==0 )  continue;
        
        DFS(nx,ny,cnt);
    }
}

int BFS(int idx)
{
    int visited[MAX][MAX]={0,};
    queue <pos> q;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j]==idx){
                q.push({i,j});
                visited[i][j]=1;
            }
        }
    }
    
    while(!q.empty()){
        int x = q.front().x;
        int y = q.front().y;
        q.pop();

        for(int k=0;k<4;k++){
            int nx = x+dx[k];
            int ny = y+dy[k];
            
            if(nx<0 || ny <0 || nx >= N || ny >= N || visited[nx][ny]!=0 )  continue;
            if(map[nx][ny] !=0 &&  map[nx][ny] != idx)  return visited[x][y]+1;
            
            visited[nx][ny]=visited[x][y]+1;
            q.push({nx,ny});
        }
    }
    return 0;
}


int main(void)
{
    cin >> N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin >> map[i][j];
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(map[i][j]==1 && !tmp[i][j]){
                cnt++;
                DFS(i,j,cnt);
            }
        }
    }
    
    for(int i=1;i<cnt;i++)  {
        int res =BFS(i);
        if(res!=0 && res < answer)  answer =res;
    }
    cout << answer-2;
    return 0;
}