[백준/C++] 2146 번 : 다리 만들기 풀이

문제 2146 : 다리 만들기

문제 링크 : https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

 

문제

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.

이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.

위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.

물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).

지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.

 

입력

첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.

 

출력

첫째 줄에 가장 짧은 다리의 길이를 출력한다.

 

 

위 문제는 DFS, BFS 모두 사용해야 하는 문제이다.

 

1️⃣ 먼저 DFS 탐색을 사용해 각 섬의 영역을 숫자로 표시한다.

1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0

위 그래프는 DFS 탐색을 마치면

1 1 1 0 0 0 0 2 2 2 
1 1 1 1 0 0 0 0 2 2 
1 0 1 1 0 0 0 0 2 2 
0 0 1 1 1 0 0 0 0 2 
0 0 0 1 0 0 0 0 0 2 
0 0 0 0 0 0 0 0 0 2 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 3 3 0 0 0 0 
0 0 0 0 3 3 3 0 0 0 
0 0 0 0 0 0 0 0 0 0 

위와 같이 영역이 번호로 표시된다.

 

 

2️⃣ BFS 탐색을 이용하여 각 섬에서 다른 섬으로 가는 최소 거리를 구한 뒤, 이 중 최소를 출력한다.
주의할 점은 현재 queue의 size 만큼 for문을 돌린 다음 result를 1 증가 시키는 것이다.

 

 

아래는 코드입니다.

#include <iostream>
#include <queue>
#include <cstring>

#define MAX 101
#define INF 987654321

using namespace std;

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

int n;
int map[MAX][MAX];
bool visited[MAX][MAX] = {false,};
int result;

int min(int a, int b){
    return a < b ? a : b;
}

void dfs(int y, int x, int cnt){
    visited[y][x] = true;
    map[y][x] = cnt;

    for(int i=0; i<4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];

        if(ny<0 || nx<0 || ny>=n || nx>=n) continue;
        if(!visited[ny][nx] && map[ny][nx]) dfs(ny,nx,cnt);
    }
}

void bfs(int cnt){
    queue <pair<int,int>> que;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(map[i][j] == cnt){
                visited[i][j] = true;
                que.push(make_pair(i,j));
            }
        }
    }
    
    while(!que.empty()){
        int cursize = que.size();
        
        for(int i=0; i<cursize; i++){
            int y = que.front().first;
            int x = que.front().second;
            que.pop();
            
            for(int i=0; i<4; i++){
                int ny = y + dy[i];
                int nx = x + dx[i];
                
                if(ny<0 || nx<0 || ny>=n || nx>=n) continue;
                if(map[ny][nx] && map[ny][nx] != cnt) return;
                else if (!map[ny][nx] && !visited[ny][nx]) {
                    visited[ny][nx] = true;
                    que.push(make_pair(ny, nx));
                }
            }
            
        }
        result++;
    }
}



int main(void){

    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> 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]) {
                cnt++;
                dfs(i,j,cnt);
            }
        }
    }
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << map[i][j] << " ";
        }
        cout << endl;
    }
    
    int ans = INF;
    
    for(int i=1; i<cnt; i++){
        memset(visited, false, sizeof(visited));
        result = 0;
        bfs(i);
        ans = min(ans, result);
        
    }
    cout << ans << endl;

    return 0;
}

 

 

 

풀이 인증