[백준] 2146: 다리 만들기

0. 문제 주소

 

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

2146번: 다리 만들기

 

 

1. 풀이

 

귀찮지만 실수 없이 코드 짜는 연습 하기 좋은 문제.

총 4개의 배열을 사용한다.

int grid[MAX][MAX];
int conti[MAX][MAX];
int dist[MAX][MAX];
bool visited[MAX][MAX];

1과 0으로 구분된 원래 지도를 나타내는 grid 배열,

DFS를 이용해 대륙별 번호를 매긴 conti 배열,

각 대륙에서부터 거리를 나타내는 dist 배열,

순회간 방문 여부를 나타내는 visited 배열.

 

크게 어려운 점은 없었지만 아쉬운 점은 0ms가 걸린 풀이가 있던 반면에 내 코드는 904ms가 걸렸다. 모든 대륙에서 각각 출발하는 BFS를 전부 돌린게 원인인 것 같다.

 

 

2. 풀이 코드

 

* 유의할 점

1. dist 배열의 활용 : conti 배열을 순회하면서 0을 만날 때마다 인접한 곳을 바로 감소시키면 안 됨

2. 배열의 초기화 시점

 

#include <bits/stdc++.h>
#define pii pair<int, int>
#define MAX 105
#define INF 987654321

using namespace std;

int N;
int grid[MAX][MAX];
int conti[MAX][MAX];
int dist[MAX][MAX];
bool visited[MAX][MAX];
int di[] = {0, 0, -1, 1};
int dj[] = {-1, 1, 0, 0};
int ans = INF;

void DFS(int i, int j, int num){
    visited[i][j] = true;
    conti[i][j] = num;

    for (int d=0;d<4;d++){
        int ni = i + di[d], nj = j + dj[d];
        if (ni <= 0 || ni > N || nj <= 0 || ni > N || visited[ni][nj] || grid[ni][nj] == 0) continue;
        DFS(ni, nj, num);
    }
}


int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    scanf("%d", &N);
    for (int i=1;i<=N;i++){
        for (int j=1;j<=N;j++){
            scanf("%d", &grid[i][j]);
        }
    }
    int conti_num = 0;
    for (int i=1;i<=N;i++){
        for (int j=1;j<=N;j++){
            if (!visited[i][j] && grid[i][j]){
                conti_num++;
                DFS(i, j, conti_num);
            }
        }
    }

    for (int n=1;n<=conti_num;n++){
        int curr_min = INF;
        memset(visited, 0, sizeof(visited));
        for (int i=1;i<=N;i++){
            for (int j=1;j<=N;j++){
                dist[i][j] = INF;
            }
        }

        queue<pii> q;
        for (int i=1;i<=N;i++){
            for (int j=1;j<=N;j++){
                if (conti[i][j] == n){
                    q.push(pii(i, j));
                    visited[i][j] = true;
                    dist[i][j] = 0;
                }
            }
        }
        while(!q.empty()){
            int i = q.front().first, j = q.front().second;
            q.pop();
            for (int d=0;d<4;d++){
                int ni = i + di[d], nj = j + dj[d];
                if (ni <= 0 || ni > N || nj <= 0 || nj > N || visited[ni][nj]) continue;
                dist[ni][nj] = min(dist[ni][nj], dist[i][j] + 1);
                q.push(pii(ni, nj));
                visited[ni][nj] = true;
            }
        }

        for (int i=1;i<=N;i++){
            for (int j=1;j<=N;j++){
                if (conti[i][j] > 0 && conti[i][j] != n){
                    curr_min = min(curr_min, dist[i][j]);
                }
            }
        }
        ans = min(ans, curr_min);
    }
    printf("%d\n", ans - 1);

}