[2146] 다리 만들기

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

2146번: 다리 만들기

<문제>

쉬워보이지만, 생각보단 쉽지 않다. 떠올릴만한 효율적인 알고리즘들은 대부분 반례로 저격당한다.

결국, 일일히 하나씩 bfs를 돌려봐야 하는데, 사용 알고리즘은 다음과 같다.

 

입력에는 여러개의 섬이 존재한다.

섬의 개수가 M개 있다면, 이들에 각각 이름을 붙여준다. 1번섬, 2번섬, 3번섬...M번섬으로 하자.

1) 1번섬에서 이을 수 있는 다리의 최단길이를 알아보기 위해, 1번섬을 기준으로 bfs를 돌린다.
bfs의 종료조건은, 1번섬도 아니고 바다도 아닌, 다른 2~M번섬을 만날때이다.

2) 2번섬을 기준으로의 최단거리를 찾기위해 1)과 같은 방법으로 bfs를 돌린다. 이처럼 M개의 섬에 대해 M번 반복한다.

3) M번 반복한 결과중 어느것 하나 이상은(실제로는 최소 2번이상의 최적해를 탐색하게 된다) 최적해다. bfs의 결과를
정답을 담을 변수에 항상 최소값으로 업데이트하면 답을 찾는다.

-> for (i = 1; i <= M; i++)
          answer = min(bfs(i), answer);

 

다만, 이 알고리즘을 수행하기 전에 사전처리를 해주어야 하는 부분이 있다.

1) 입력으로 섬이 구분되어 있지 않다. 이들에 1~M의 이름을 붙이는 일을 수행해야한다.
물론 M도 주어지지 않으므로 직접 카운트해야한다.

 

<소스코드>

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
queue <pair<int, int>>initQ;
queue <pair<int, int>>q;
int a[101][101], n, dy[4] = { 0,1,0,-1 }, dx[4] = { 1,0,-1,0 };
bool visit[101][101];
void initBfs(int sy, int sx, int keyNumber) {//단지번호 붙이기
    int y, x, ty, tx, i;
    while (!initQ.empty())initQ.pop();
    memset(visit, false, sizeof(visit));
    initQ.push({ sy,sx });
    a[sy][sx] = keyNumber;
    visit[sy][sx] = true;
    while (!initQ.empty()) {
        ty = initQ.front().first;
        tx = initQ.front().second;
        initQ.pop();
        for (i = 0; i < 4; i++) {
            y = ty + dy[i];
            x = tx + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= n)continue;
            if (a[y][x] == 1 && visit[y][x] == false) {
                visit[y][x] = true;
                a[y][x] = keyNumber;
                initQ.push({ y,x });
            }
        }
    }
}
int bfs(int keyNumber) {//keyNumber 섬을 포함하는 최단다리 탐색
    int i, j, k, y, x, ty, tx,dist=0;
    memset(visit, false, sizeof(visit));
    while (!q.empty())q.pop();
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (a[i][j] == keyNumber){
                q.push({ i,j });
                visit[i][j] = true;
            }
        }
    }
    dist = 0;
    while (!q.empty()) {
        int qSize = q.size();
        for (int d = 0; d < qSize; d++) {
            ty = q.front().first;
            tx = q.front().second;
            q.pop();
            for (i = 0; i < 4; i++) {
                y = ty + dy[i];
                x = tx + dx[i];
                if (y < 0 || x < 0 || y >= n || x >= n || a[y][x] == keyNumber)continue;
                if (a[y][x] != -1 && a[y][x] != keyNumber) {
                    return dist;
                }
                if (a[y][x] == -1 && visit[y][x] == false) {
                    q.push({ y,x });
                    visit[y][x] = true;
                }
            }
        }
        dist++;
    }
    return 123456;
}
int main(void) {
    int i, j, k;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &a[i][j]);
            if (a[i][j] == 0) {
                a[i][j] = -1;//바다는 -1
            }
        }
    }
    int landCnt = 1;
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (a[i][j] == 1 && visit[i][j] == false) {
                initBfs(i, j, landCnt);//단지번호붙이기
                landCnt++;
            }
        }
    }
    landCnt--;
    int answer = 123456;
    for (i = 1; i <= landCnt; i++)
        answer = min(bfs(i), answer);
    printf("%d", answer);
    return 0;
}