다리 만들기

• 모든 좌표에 대해 bfs를 하는 것 보다는 거리를 구하는 것이 더 빠르다 (내 풀이)

• 나의 풀이 로직
  1) 각 섬의 개수 별로 섬의 모든 좌표를 저장한 queue를 구한다
  2) 모든 섬에 대해 각 섬의 모든 좌표들 간 거리를 구해서 최소값을 갱신한다

• 많은 사람들의 풀이 로직
  1) 각 섬을 1~n으로 카운팅해서 모든 좌표를 구한다
  2) 모든 섬에 대해 각 섬의 모든 좌표에서 bfs를 실행!
  (board[][]값이 0인 경우 즉, 바다인 경우에만 queue에 넣어서 점점 넓혀간다! 그러다가 현재 섬과 다른 번호를 만나면 stop! 이렇게 모든 좌표에 대해 실행해서 최소값을 갱신한다!)

코드

#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;

int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    int board[N][N];
    int vis[N][N];
    for(int i=0;i<N;i++) {
        fill(board[i], board[i]+N, 0);
        fill(vis[i], vis[i]+N, 0);
        for(int j=0;j<N;j++){
            cin >> board[i][j];
        }
    }
    vector<vector<pair<int,int>>> v;
    int part = -1;

    /* 각 섬에 해당되는 좌표들을 저장 및 분류 */
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(vis[i][j] || board[i][j] == 0) continue;
            queue<pair<int,int>> q;
            q.push({i,j});
            vis[i][j] = 1;
            part++;
            vector<pair<int,int>> temp; temp.push_back({i,j});
            v.push_back(temp);
            while(!q.empty())
            {
                auto cur = q.front(); q.pop();
                for(int dir=0;dir<4;dir++)
                {
                    int ny = cur.first + dy[dir];
                    int nx = cur.second + dx[dir];
                    if(ny<0 or nx<0 or ny>=N or nx>=N) continue;
                    if(vis[ny][nx] || board[ny][nx] == 0) continue;
                    q.push({ny,nx});
                    vis[ny][nx] = 1;
                    v[part].push_back({ny,nx});
                }
            }

        }
    }

    /* 각 섬에 있는 좌표들 간 최소 거리를 구한다 */
    int ans = N+N; // 크기가 N일 때 최대 N+N까지 커질 수 있음
    for(int i=0;i<v.size()-1;i++)
    {
        for(int j=i+1;j<v.size();j++)
        {
            int MIN = N+N; // 크기가 N일 때 최대 N+N까지 커질 수 있음
            for(int k=0;k<v[i].size();k++)
            {
                auto fix = v[i][k];
                for(int q=0;q<v[j].size();q++)
                {
                    auto comp = v[j][q];
                    int val = abs(fix.first-comp.first) + abs(fix.second-comp.second) -1;
                    MIN = min(MIN,val);
                }
            }
            ans = min(MIN, ans);
        }
    }
    cout << ans;
    return 0;
}