[백준]2146번 다리 만들기 - C++

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

2146번: 다리 만들기

문제

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

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

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

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

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

입력

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

출력

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

---

 

1. dfs로 대륙 번호 붙이기

2.각 칸별로 bfs로 다른 대륙과의 최단거리 찾기

    - 바다인 경우 큐에 추가

    - 다른 대륙인 경우 우선순위 큐 이므로 가장 짧은 거리를 통해 도착한 상황이므로 ans 최신화 후 bfs 종료

    - 같은 대륙인 경우는 패스

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

using namespace std;
#define MIN(a,b) a > b ? b : a 
typedef pair<int,pair<int,int> > point;
int N,a,cnt = 1,ans = 987654321;
int mat[110][110];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
bool vis[110][110];

void dfs(int x, int y){
    mat[x][y] = cnt;
    for(int k = 0 ; k < 4 ; k++){
        if(mat[x + dx[k]][y + dy[k]] > 0 && !vis[x + dx[k]][y + dy[k]]){
            vis[x + dx[k]][y + dy[k]] = true;
            dfs(x + dx[k],y + dy[k]);
        }
    }
}

void bfs(int x, int y, int land){
    priority_queue < point, vector<point>, greater<point> > q;
    q.push(make_pair(0,make_pair(x,y)));
    memset(vis,false,sizeof(vis));
    vis[x][y] = true;
    while(!q.empty()){
        int curdis = q.top().first;
        int curx = q.top().second.first;
        int cury = q.top().second.second;
        q.pop();
        for(int k = 0 ; k < 4 ; k++){
            if(mat[curx + dx[k]][cury + dy[k]] != -1 && !vis[curx + dx[k]][cury + dy[k]]){
                if(mat[curx + dx[k]][cury + dy[k]] == 0){
                    vis[curx + dx[k]][cury + dy[k]] = true;
                    q.push(make_pair(curdis + 1, make_pair(curx + dx[k],cury + dy[k])));
                }
                else if(mat[curx + dx[k]][cury + dy[k]] != land){
                    ans = MIN(ans,curdis);
                    return;
                }
            }
            
        }
    }

}

int main (){
    cin >> N;
    for(int i = 1 ; i <= N ; i++){
        for(int j = 1 ; j <= N ; j++){
            cin >> a;
            mat[i][j] = a;
        } 
    }
    for(int i = 0 ; i <= N + 1; i++){
        mat[i][0] = -1;
        mat[0][i] = -1;
        mat[N+1][i] = -1;
        mat[i][N+1] = -1;
    }

    for(int i = 1 ; i <= N; i++){
        for(int j = 1 ; j <= N; j++){
            if(mat[i][j] > 0 && !vis[i][j]){
                vis[i][j] = true;
                dfs(i,j);
                cnt++;
            }
        }
    }
    
    for(int i = 1 ; i <= N; i++){
        for(int j = 1 ; j <= N; j++){
            if(mat[i][j] > 0){
                bfs(i,j,mat[i][j]);
            }
        }
    }
    cout << ans;
}

---

처음에 생각한 풀이가 맞았으나 자잘한 실수가 많았다.

1. 초기화를 [i][0] [0][i]만 함

2. bfs 0~ N-1 까지 돌림

3. curx/cury 에다가 dx/dy 더해야 하는데  x/y 에다가 더함

4. curx cury pop() 안 함

5. vis 초기화해야 되는데 mat 초기화해서 판 초기화함.

정신을 놓고 풀지 않았는데 이런 자잘한 실수를 하는 실력 부족이었다. 종종 하는 실수들도 있고 처음 하는 실수도 있는데 앞으로 더 유의해야겠다!