[백준 2146번] 다리 만들기

소스코드

---

#include <iostream>
using namespace std;
 
// 0은 바다, 1은 육지
int n, map[101][101], visit[101][101], cnt=2;
int que[10001], h, t, cque[10001], ch,ct;
int Min = 98765432;
 
void visitInit() {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            visit[i][j] = 0;
}
 
void bfs() {
    while (h != t){
        int pos = que[h++];
        int x = pos / 1000;
        int y = pos % 1000;
 
        if (x - 1 >= 0 && visit[x - 1][y] == 0) {
            if (map[x - 1][y]==1){
                que[t++] = (x - 1) * 1000 + y;
                visit[x - 1][y] = 1;
            }
            else if(map[x-1][y]==0) {
                map[x][y] = cnt;
            }
        }
        if (x + 1 < n && visit[x + 1][y] == 0) {
            if (map[x + 1][y]==1) {
                que[t++] = (x + 1) * 1000 + y;
                visit[x + 1][y] = 1;
            }
            else if(map[x+1][y]==0){
                map[x][y] = cnt;
            }
        }
        if (y - 1 >= 0 && visit[x][y-1] == 0) {
            if (map[x][y - 1]==1) {
                que[t++] = x * 1000 + (y-1);
                visit[x][y-1] = 1;
            }
            else if(map[x][y-1]==0){
                map[x][y] = cnt;
            }
        }
        if (y + 1 < n && visit[x][y + 1] == 0) {
            if (map[x][y + 1]==1) {
                que[t++] = x * 1000 + (y + 1);
                visit[x][y + 1] = 1;
            }
            else if(map[x][y+1]==0){
                map[x][y] = cnt;
            }
        }
        
    }
}
 
 
int minPath(int myNum) {
    while (h != t) {
        int pos = que[h++];
        int x = pos / 1000;
        int y = pos % 1000;
        int c = cque[ch++];
 
        if (x - 1 >= 0 && visit[x - 1][y] == 0) {
            if (map[x - 1][y] == 0) {
                que[t++] = (x - 1) * 1000 + y;
                cque[ct++] = c + 1;
                visit[x - 1][y] = 1;
            }
            else if (map[x - 1][y] != myNum && map[x-1][y]!=1) {
                return c;
            }
        }
        if (x + 1 < n && visit[x + 1][y] == 0) {
            if (map[x + 1][y] == 0) {
                que[t++] = (x + 1) * 1000 + y;
                cque[ct++] = c + 1;
                visit[x + 1][y] = 1;
            }
            else if (map[x + 1][y] != myNum&& map[x + 1][y] != 1) {
                return c;
            }
        }
        if (y - 1 >= 0 && visit[x][y-1] == 0) {
            if (map[x][y-1] == 0) {
                que[t++] = x * 1000 + (y-1);
                cque[ct++] = c + 1;
                visit[x][y-1] = 1;
            }
            else if (map[x][y - 1] != myNum&& map[x][y-1] != 1) {
                return c;
            }
        }
        if (y + 1 < n && visit[x][y + 1] == 0) {
            if (map[x][y + 1] == 0) {
                que[t++] = x * 1000 + (y + 1);
                cque[ct++] = c + 1;
                visit[x][y + 1] = 1;
            }
            else if (map[x][y + 1] != myNum && map[x][y+1] != 1) {
                return c;
            }
        }
    }
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> map[i][j];
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n;j++)
            if (map[i][j]==1 && visit[i][j]==0) {
                h = 0, t = 0;
                que[t++] = i * 1000 + j;
                bfs();
                cnt++;
            }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j]>1) {
                h = 0, t = 0, ch=0, ct=0;
                visitInit();
                que[t++] = i * 1000 + j;
                cque[ct++] = 1;
                int ret = minPath(map[i][j]);
                if (ret < Min)
                    Min = ret;
            }
        }
    }
 
    cout << Min-1 << '\n';
    return 0;
}