[BOJ] 2146번 : 다리 만들기 (C++)

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

2146번: 다리 만들기

 

맨 처음 아이디어는 다음과 같았다.

 

1. 섬을 BFS로 찾고, 하나의 땅을 찾을 때마다 그 좌표를 각 vector에 저장한다. (vector는 섬의 개수만큼 저장됨)

2. 섬을 다 찾은 후에 1번 섬 좌표에서 2번 섬 좌표까지 중에서 4방향으로 뻗어갈 때 최단거리를 구한다.

(이 때 방법은 포문을 돌면서 i는 0~n-1까지이고 j는 i+1~n-1까지로 모든 경우를 다 따져, land[i]와 land[j]에서 하나씩 꺼내어 최소의 |x1-x2|+|y1-y2|-1 값을 구하려 했었다.)

 

 

그런데 그렇게 할 필요가 없었다. 애초에 구현을 어떻게 해야될지도 모르겠는 상황이었다. 

수정된 아이디어는 다음과 같다.

 

1. 섬을 BFS로 찾을 때 섬마다 번호를 매기면서 그 좌표를 각 vector에 저장한다. (동일하게 vector는 섬의 개수만큼 저장됨)

2. 섬을 다 찾은 후에 1번 섬 vector부터 차례로 "좌표 전부"를 거리를 구하기 위한 새로운 큐에 넣는다. 즉, 같은 섬에 속한 육지에 대해 BFS를 동시에 돌리는 것이다. 여러 개의 시작점에서 BFS를 돌리고 싶은 경우 일단 큐에 전부 넣고, 이후로는 늘 하던대로 하면 된다. ("BFS 특성상 큐에 쌓이는 순서는 반드시 거리 순"이기 때문이다!!)

3. 한칸씩 전진하며 번호를 통해 같은 땅인지를 확인하고 아니라면 값을 증가시켜 전진한다. 다른 섬이 나올 때까지 BFS를 돌려주면 된다. 

 

수정된 아이디어에서 추가된 아이디어는 visited 배열에 섬의 번호를 넣어서 초기화를 계속 해줄 필요를 없게 만든 것도 있다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
using namespace std;
#define X first
#define Y second

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

int n; 
int idx;
int area[102][102];
int visited[102][102];
queue<pair<int,int>> q;
vector<pair<int,int>> land[10002]; //i번째 섬에 포함된 땅의 좌표들의 vector

bool OOB(int x, int y){
    return x<0||x>=n||y<0||y>=n;
}

void BFS(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(visited[i][j] || area[i][j]==0) continue;

            idx++;
            land[idx].push_back({i,j});
            area[i][j]=idx; //몇번째 땅인지 표시
            visited[i][j]=1;
            q.push({i,j});

            while(!q.empty()){
                auto cur = q.front();
                q.pop();

                for(int dir=0; dir<4; dir++){
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];
                    if(nx<0||nx>=n||ny<0||ny>=n) continue;
                    if(visited[nx][ny]||area[nx][ny]==0) continue;

                    land[idx].push_back({nx,ny});
                    area[i][j]=idx;
                    visited[nx][ny]=1;
                    q.push({nx,ny});
                }
            }
        }
    }
}

int min_bridge(int idx){
    //idx번째 섬에서 최단 거리의 다리 구하기
    //BFS 특성상 "큐에 쌓이는 순서는 반드시 거리 순" 이므로
    
    queue<pair<pair<int,int>,int>> q;

    //vector에 저장해놨던 애들을 꺼내어 한번에 큐에 넣어줌
    //queue는 "x,y좌표" 그리고 "거리"를 저장함
    //이로써 하나의 섬의 모든 좌표는 "동시에" 거리를 계산하게 됨
    for(auto i : land[idx]){
        visited[i.X][i.Y]=idx;
        q.push({{i.X, i.Y},0});
    }

    while(!q.empty()){
        auto cur = q.front(); q.pop();
        int t = cur.Y;

        for(int dir=0; dir<4; dir++){
            int nx = cur.X.X+dx[dir];
            int ny = cur.X.Y+dy[dir];

            if(OOB(nx,ny)) continue; //범위를 벗어남
            if(visited[nx][ny]==idx) continue; //이미 방문했던 좌표임
            if(area[nx][ny]==idx) continue; //같은 섬일 경우
            if(area[nx][ny]!=0) return t; //바다가 아니란 것은 다른 섬이라는 의미
            //남은 경우는 area[nx][ny]==0인 경우밖에 없음
            visited[nx][ny]=idx;
            q.push({{nx,ny},t+1});
        }
    }
    //다른 섬을 못만난 경우 큰 값을 반환함
    return 99999;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>area[i][j];
        }
    }

    BFS(); //*여기서 땅마다 번호를 매겨줘야함.. 

    //초기화안해도됨
    for(int i=0; i<n; i++) {
        fill(visited[i], visited[i]+n, -1);
    }

    int ans = 0x7fffffff;
    for(int i=1; i<=idx; i++){
        ans = min(ans, min_bridge(i));
    }
    
    cout<<ans;

    return 0;
}

 

하나의 섬을 찾을 때마다 모든 좌표를 각 벡터에 저장해야한다는 것은 혼자서도 잘 캐치하였으나,

1. 섬을 구분하기 위해 섬마다 번호를 매긴다.

2. 각 vector에서 꺼낸 좌표로 각각을 거리를 구하기 위한 BFS로 돌린다.

3. BFS로 돌릴 때, queue<pair<pair<int,int>,int>>를 이용하여 거리값도 함께 관리하며 모든 좌표를 한번에 큐에 넣는다.

4. BFS로 돌릴 때, visted배열을 매번 초기화하지 않기 위해 visited값을 섬의 인덱스로 둔다.

이 아이디어들을 생각해내지 못했다. 

특히, 1번과 3번은 매우 중요한 부분이었는 생각해내지 못해서 아쉽다. 

 

소스는 아래의 소스코드를 참고하였다.

https://www.acmicpc.net/source/share/f69dc26b14f24aa688292be57697e7e2

 

 

O(N^2)에 푸는 코드도 있다. 

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x09/solutions/2146_1.cpp