BOJ 2146번 다리 만들기

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/2146/2146/%EC%86%8C%EC%8A%A4.cpp

 

탐색은 역시 재밌는거 같다.

다리 만들기는 떨어진 지역(?) 간의 연결을 할 수 있는 최소 칸을 구하는 문제이다.

풀어낸 과정을 간략해보면

1) 일단 모든 지역을 재정의했다. 지역1, 지역2, 지역3, .. 이런식으로

2) 1)과정에서 주변에 바다가 있을 경우 임의의 큐에 넣어준다. (다리를 연결하기 위한 시작점이 된다)

3) 2)과정에서 만들어진 큐를 이용하여 좌표를 하나씩 꺼내어 다른 지역을 찾는다.

4) Min 이 설정이 되면 그 다음부터는 탐색간 다리가 Min과 같아지게되면 더이상 탐색할 필요가 없으니 중지시킨다.

 

이정도 과정이면 이 문제를 해결하는데 문제가 없을 것 같다.

 

#include <iostream>
#include <queue>
using namespace std;
 
typedef pair<pair<int, int>, int> pii;
int mx[4] = { 1,-1,0,0 };
int my[4] = { 0, 0, 1, -1 };
int N;
int arr[100][100];
int visit[100][100];
queue<pair<int,int> > q;
queue<pair<int, int> > qq;
queue<pii> qqq;
 
bool location(int y, int x) {
    for (int i = 0; i < 4; i++) {
        int yy = my[i] + y;
        int xx = mx[i] + x;
        if (yy >= 0 && yy < N && xx >= 0 && xx < N && !arr[yy][xx]) return true;
    }
    return false;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++) {
            cin >> arr[i][k];
        }
    }
 
    int land = 2;
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < N; k++) {
            if (arr[i][k] && !visit[i][k]) {
                qq.push({i,k});
                arr[i][k] = land;
                while (!qq.empty()) {
                    int y = qq.front().first;
                    int x = qq.front().second;
                    qq.pop();
 
                    if (location(y, x)) q.push({y,x});
                    for (int j = 0; j < 4; j++) {
                        int yy = my[j] + y;
                        int xx = mx[j] + x;
                        if (yy >= 0 && yy < N && xx >= 0 && xx < N && arr[yy][xx] == 1) {
                            qq.push({ yy,xx });
                            arr[yy][xx] = land;
                            visit[yy][xx] = 1;
                        }
                    }
                }
                land++;
            }
        }
    }
 
     int Min = 10000000;
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        bool check = false;
        land = arr[y][x];
        q.pop();
        qqq.push({ {y,x},0 });
        while (!qqq.empty()) {
            int yy = qqq.front().first.first;
            int xx = qqq.front().first.second;
            int cnt = qqq.front().second;
            qqq.pop();
            
            if (cnt >= Min) {
                while (!qqq.empty()) qqq.pop();
                break;
            }
 
            for (int i = 0; i < 4; i++) {
                int yyy = my[i] + yy;
                int xxx = mx[i] + xx;
                if (yyy >= 0 && yyy < N && xxx >= 0 && xxx < N) {
                    if (arr[yyy][xxx] == 0) {
                        arr[yyy][xxx] = 1;
                        qqq.push({ {yyy,xxx},cnt + 1 });
                        qq.push({ yyy,xxx });
                    }
                    else if (arr[yyy][xxx] != 1 && arr[yyy][xxx] != land) {
                        check = true;
                        Min = Min > cnt ? cnt : Min;
                        break;
                    }
                }
            }
            if (check) {
                while (!qqq.empty())qqq.pop();
            }
        }
        while (!qq.empty()) {
            int yy = qq.front().first;
            int xx = qq.front().second;
            qq.pop(); arr[yy][xx] = 0;
        }
    }
 
    if (Min == 10000000) Min = 0;
    cout << Min;
    return 0;
}