[BOJ-2146]다리만들기

[출처]

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

[문제요약]

입력으로 육지(1)와 바다(0)가 주어지며, 서로 다른 육지를 잇기 위해 놓아야 하는 최소한의 다리(칸)을 구한다.

[입력]

N ~ 지도의 사이즈 N~[1,100] N*N

지도의 정보(육지(1), 바다(0)) 이 주어진다.

[출력] 

서로 다른 육지를 잇기 위해 놓아야 하는 최소한의 다리 갯수를 구한다.

[접근방법]

BFS로 풀이하였다. 입력으로 주어지는 지도의 정보는 0과 1, 바다와 육지로 구분되어 있다. 

이를 통해, 서로 다른 육지를 구분하기 위해서 BFS 1회,

그리고 구분된 육지를 기준으로 다른 육지를 도달하기위한 최소값을 구하기 위한 BFS 1회

총 BFS 2회로 문제를 풀이하였다.

처음 문제를 풀었을 때 952ms  에서 불필요한 탐색을 제거하여 56ms로 풀이할 수 있었다.

[C++11 source code BFS]

#include<cstdio>
#include<queue>
#include<memory.h>
#define din1(a) scanf("%d", &a)
using namespace std;
 
const int M = 111;
const int INF = 1111;
const int dr[] = {0, 1, 0, -1};
const int dc[] = {1, 0, -1, 0};
int imap[M][M];
int place[M][M];
int N;
int ans;
 
struct pos {
    int R;
    int C;
    pos(int ir, int ic) : R(ir), C(ic) {}
};
 
void print_place() {
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            printf("%3d", place[r][c]);
        }
        puts("");
    }
}
 
void make_place(int r, int c, int no) {
    queue<pos> Q;
    Q.push(pos(r, c));
    place[r][c] = no;
    while (!Q.empty()) {
        pos here = Q.front(); Q.pop();
 
        for (int i = 0; i < 4; i++) {
            int tr = here.R + dr[i];
            int tc = here.C + dc[i];
            if (0 <= tr && tr < N && 0<= tc && tc< N){
                if (imap[tr][tc] == 1 && place[tr][tc] == 0) {
                    place[tr][tc] = no;
                    Q.push(pos(tr, tc));
                }
            }
        }
    }
}
 
int process(int r, int c) {
    queue<pos> Q;
    Q.push(pos(r, c));
    int board[M][M];
    int ret = INF;
    for (int rr = 0; rr < N; rr++) {
        for (int cc = 0; cc < N; cc++) {
            board[rr][cc] = INF;
        }
    }
    
    memset(board, 0, sizeof(board));
    int pivot = place[r][c];
    while (!Q.empty()) {
        pos here = Q.front(); Q.pop();
                
        for (int i = 0; i < 4; i++) {
            int tr = here.R + dr[i];
            int tc = here.C + dc[i];
            int mov = board[here.R][here.C] + 1;
            if(mov > ans) return ret; // add code ; 56ms
            if (0 <= tr && tr < N && 0 <= tc && tc < N) {
                if (place[tr][tc] != pivot && board[tr][tc] == 0) {
                    board[tr][tc] = mov;
                    if (pivot != place[tr][tc] && place[tr][tc] != 0) ret = (ret > mov-1) ? mov-1 : ret;
                    Q.push(pos(tr, tc));
                }
            }
        }
    }
 
    return ret;
}
 
int main() {    
    ans = INF;
    din1(N);
 
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            din1(imap[r][c]);
        }
    } // input
    
    int no = 1;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            if (place[r][c] == 0 && imap[r][c] == 1) make_place(r, c, no++);
        }
    }
 
    //print_place();
 
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            if (place[r][c] != 0) {
                int tmp = process(r, c);
                ans = (tmp > ans)? ans : tmp;
            }
        }
    }
 
    printf("%d", ans);
    
    return 0;
}

#include<cstdio>
#include<queue>
#include<memory.h>
#define din1(a) scanf("%d", &a)
using namespace std;
 
const int M = 111;
const int INF = 1111;
const int dr[] = {0, 1, 0, -1};
const int dc[] = {1, 0, -1, 0};
int imap[M][M];
int place[M][M];
int N;
int ans;
 
struct pos {
    int R;
    int C;
    pos(int ir, int ic) : R(ir), C(ic) {}
};
 
void print_place() {
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            printf("%3d", place[r][c]);
        }
        puts("");
    }
}
 
void make_place(int r, int c, int no) {
    queue<pos> Q;
    Q.push(pos(r, c));
    place[r][c] = no;
    while (!Q.empty()) {
        pos here = Q.front(); Q.pop();
 
        for (int i = 0; i < 4; i++) {
            int tr = here.R + dr[i];
            int tc = here.C + dc[i];
            if (0 <= tr && tr < N && 0<= tc && tc< N){
                if (imap[tr][tc] == 1 && place[tr][tc] == 0) {
                    place[tr][tc] = no;
                    Q.push(pos(tr, tc));
                }
            }
        }
    }
}
 
int process(int r, int c) {
    queue<pos> Q;
    Q.push(pos(r, c));
    int board[M][M];
    int ret = INF;
    for (int rr = 0; rr < N; rr++) {
        for (int cc = 0; cc < N; cc++) {
            board[rr][cc] = INF;
        }
    }
    
    memset(board, 0, sizeof(board));
    int pivot = place[r][c];
    while (!Q.empty()) {
        pos here = Q.front(); Q.pop();
                
        for (int i = 0; i < 4; i++) {
            int tr = here.R + dr[i];
            int tc = here.C + dc[i];
            int mov = board[here.R][here.C] + 1;
            if (0 <= tr && tr < N && 0 <= tc && tc < N) {
                if (place[tr][tc] != pivot && board[tr][tc] == 0) {
                    board[tr][tc] = mov;
                    if (pivot != place[tr][tc] && place[tr][tc] != 0) ret = (ret > mov-1) ? mov-1 : ret;
                    Q.push(pos(tr, tc));
                }
            }
        }
    }
 
    return ret;
}
 
int main() {    
    ans = INF;
    din1(N);
 
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            din1(imap[r][c]);
        }
    } // input
    
    int no = 1;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            if (place[r][c] == 0 && imap[r][c] == 1) make_place(r, c, no++);
        }
    }
 
    //print_place();
 
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            if (place[r][c] != 0) {
                int tmp = process(r, c);
                ans = (tmp > ans)? ans : tmp;
            }
        }
    }
 
    printf("%d", ans);
    
    return 0;
}