백준 2146 / 다리 만들기

우선 섬을 둘러싼 0들을 

(섬넘버, x좌표, y좌표)로 받고

섬 넘버가 다른 좌표끼리의 최소 거리를 구하는 게 끔 짰다.

시간초과가 떠서 별짓을 다했다.

10

01 

같은 여러 반례들도 처리하느라 힘들었다.

#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<tuple>
#include<memory.h>
 
using namespace std;
 
int n;
int map[101][101];
bool check[101][101];
int d[101][101];
int ans = 200000000;
 
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
 
queue<tuple<int, int, int>>beach;
vector<tuple<int, int, int>>gbeach;
queue<pair<int, int>>q;
vector<pair<int, int>>gq;
 
void go(int x, int y) {
 
    queue<pair<int, int>>q2;
 
    q2.push(make_pair(x, y));
 
    d[x][y] = 1;
    
    while (!q2.empty()) {
        int xx = q2.front().first;
        int yy = q2.front().second;
        q2.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = xx + dx[i];
            int ny = yy + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
 
                if (map[nx][ny] == 0 && d[nx][ny] == -1) {
 
                    d[nx][ny] = d[xx][yy] + 1;
 
                    q2.push(make_pair(nx, ny));
 
                }
 
            }
        }
    }
    return;
}
 
void islandmake(int num, int i, int j) {
 
    queue<pair<int, int>>oneis;
 
    oneis.push(make_pair(i, j));
 
    
 
    while (!oneis.empty()) {
        int x = oneis.front().first;
        int y = oneis.front().second;
        oneis.pop();
 
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
                if (map[nx][ny] == 1 && check[nx][ny] == false) {
                    check[nx][ny] = true;
 
                    oneis.push(make_pair(nx, ny));
                }
                if (map[nx][ny] == 0 && check[nx][ny] == false) {
 
                    beach.push(make_tuple(num, nx, ny));
                    gbeach.push_back(make_tuple(num, nx, ny));
                }
            }
        }
    }
    return;
}
 
 
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%1d", &map[i][j]);
        }
    }
    
    int num = 1;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] == 1 && check[i][j]==false) {
                check[i][j] = true;
                
                islandmake(num,i,j);
                num++;
            }
        }
    }
 
    while (!beach.empty()) {
        int numa, x, y;
 
        tie(numa, x, y) = beach.front();
        
        memset(d, -1, sizeof(d));
        go(x, y);
 
        for (int i = 0; i < gbeach.size(); i++) {
            int num2, x2, y2;
            tie(num2, x2, y2) = gbeach[i];
 
            if (numa < num2) {
                
                if(d[x2][y2]>0)
                ans = min(ans,d[x2][y2]);
 
            }
        }
        beach.pop();
    }
 
    cout << ans;
 
 
}