[백준 2146] 다리 만들기 (BFS) (C/C++)

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <math.h>
#include <queue>
#include <vector>
using namespace std;
 
int N;
int islandCnt;
int Min = 9999999;
int map[110][110];
int visited[110][110];
 
queue<pair<int, int>> q;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < N && y < N)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
// 섬 색칠
void paint(int x, int y, int color)
{
    q.push({x, y});
    map[x][y] = color;
    
    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && map[xpos][ypos] == -1)
            {
                q.push({xpos, ypos});
                map[xpos][ypos] = color;
            }
        }    
    }
}
 
void find()
{
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            // 바다로 가는 경우 
            if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 0 && visited[xpos][ypos] == 0)
            {
                q.push({xpos, ypos});
                visited[xpos][ypos] = visited[x][y] + 1;
            }
            // 다른섬에 도착하는 경우 = 최소 
            else if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 0 && visited[xpos][ypos] == 0)
            {
                visited[xpos][ypos] = visited[x][y] + 1;
                
                int bridgeLen = visited[xpos][ypos] - 2;
                
                if(bridgeLen < Min)
                {
                    Min = bridgeLen;
                }
                
                return;
            }
        }    
    }
}
 
int main(void)
{
//    freopen("B2146_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            cin >> map[i][j];
            
            // 섬을 번호순대로 색칠하기위해 -1로 맵 수정 
            if(map[i][j] == 1)
            {
                map[i][j] = -1;
            }
        }
    }
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            if(map[i][j] == -1)
            {
                paint(i, j, ++islandCnt);
            }
        }
    }
    
    for(int k = 1; k <= islandCnt; k++)
    {
        // 초기화 
        queue<pair<int, int>> temp;
        q = temp;
        memset(visited, 0, sizeof(visited));
        
        // 다리 계산 
        for(int i = 0; i < N; i++)
        {
            for(int j = 0; j < N; j++)
            {
                // k번 섬의 좌표 삽입 
                if(map[i][j] == k)
                {
                    q.push({i, j});
                    visited[i][j] = 1;
                }
            }
        }
        
        find();
    }
    
    cout << Min;
    
    return 0;
}