[BFS] 2146번 다리 만들기

2146번 다리 만들기

 

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

 

문제

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

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

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

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

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

 

입력

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

 

출력

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

 

예제 입력

10
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

 

예제 출력

3

 

해결방법

문제를 보고 10분 정도 고민하다가 솔루션이 떠올랐다

1. BFS 탐색으로 섬의 영역에 번호를 부여함
2. 모든 육지 중, 주변에 바다가 존재한다면 거리를 구하는 BFS 탐색을 수행함
3. 자기 육지가 아니거나 바다인 경우 큐에 넣어줌
4. 자기와 영역 번호가 다른 육지를 만나면 최소값을 갱신해줌

 

 

운이 좋게 솔루션이 바로 떠올라서 시도해봤는데 한번에 맞았습니다! 가 나왔다...후훟

하지만 아래의 코드를 보면 매 BFS 탐색 마다 visited 배열을 초기화 해줘야한다

시간 초과가 발생할거라 생각했지만 결과가 잘나왔다 (시간 복잡도에 대해서는 더 공부를 해야겠다...!!)

void bfs_dist(int r,int c){
    memset(visited, false, sizeof(visited));
    int a_info = area[r][c];
    
    queue<pair<node,int>> q;
    q.push(make_pair(node(r,c), 0));
    visited[r][c] = true;
    
    while (!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int d = q.front().second;
        q.pop();
        
        if(area[x][y] != a_info && map[x][y] == 1){
            ans = min(ans,d-1);
            return;
        }
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
            
            if((area[nx][ny]!=a_info || area[nx][ny]==-1) && !visited[nx][ny]){
                q.push(make_pair(node(nx,ny), d+1));
                visited[nx][ny] = true;
            }
        }
    }
}

 

➕ 시간 복잡도에 대한 고찰

• n 의 조건은 n≦100 이다
• 영역의 특성 상, 최악의 경우는 체스판 모양으로 영역이 존재함
• 그렇다면 영역을 구하는 BFS 탐색을 수행한다면 시간 복잡도는 O(50^2)
• 또한 거리를 구하는 BFS 탐색 또한 위와 같음
• 따라서 최악의 경우의 시간 복잡도는 O(50^2 + 50^2)
• 이게 맞는지는 모르겠음....

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 101
#define INF 987654321
using namespace std;
typedef pair<int, int> node;

int n,ans,cnt;
int map[MAX][MAX];
int area[MAX][MAX];
bool visited[MAX][MAX];

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

void bfs_area(int r,int c){
    queue<node> q;
    q.push(node(r,c));
    area[r][c] = cnt;
    
    while (!q.empty()) {
        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 || nx>=n || ny<0 || ny>=n) continue;
            
            if(area[nx][ny]==-1 && map[nx][ny]==1){
                q.push(node(nx,ny));
                area[nx][ny] = cnt;
            }
        }
    }
}

bool is_adjacentSea(int x,int y){
    for(int i=0; i<4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
        
        if(map[nx][ny]==0) return true;
    }
    return false;
}

void bfs_dist(int r,int c){
    memset(visited, false, sizeof(visited));
    int a_info = area[r][c];
    
    queue<pair<node,int>> q;
    q.push(make_pair(node(r,c), 0));
    visited[r][c] = true;
    
    while (!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int d = q.front().second;
        q.pop();
        
        if(area[x][y] != a_info && map[x][y] == 1){
            ans = min(ans,d-1);
            return;
        }
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx<0 || nx>=n || ny<0 || ny>=n) continue;
            
            if((area[nx][ny]!=a_info || area[nx][ny]==-1) && !visited[nx][ny]){
                q.push(make_pair(node(nx,ny), d+1));
                visited[nx][ny] = true;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> map[i][j];
        }
    }
    
    memset(area, -1, sizeof(area));
    
    // 영역 번호 구하기
    cnt = 1;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(area[i][j]==-1 && map[i][j]==1){
                bfs_area(i,j);
                cnt++;
            }
        }
    }
    
    // 다리 경로 구하기
    ans = INF;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(map[i][j]==1 && is_adjacentSea(i,j)){
                bfs_dist(i,j);
            }
        }
    }
    cout << ans << "\n";
}