백준, BOJ, 2146번, 다리 만들기 C++ [CPP] ★★★★

이것도 재밌고 문제로 나오지 않을까?

싶다.

 

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

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second

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

int N;
int conti[100][100];
int area[100][100];
int dist[100][100];
int flag = 1;
int minDist = INT_MAX;


void DFS(int x, int y){
    area[x][y] = flag;
    for(int dir = 0; dir<4; dir++){
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        if(nx < 0 || nx >= N || ny < 0 || ny >= N)continue;
        if(area[nx][ny] != 0)continue;
        if(conti[nx][ny] == 0)continue;
        
        DFS(nx,ny);
        
    }
}

int main(){
    cin >> N;
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            cin >> conti[i][j];
        }
    }
    
    //Grouping, 대륙 나누기
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            //육지면서 아직 area 설정이 되지 않은 곳
            if(conti[i][j] == 1 && area[i][j] == 0){
                DFS(i,j);
                flag++;
            }
        }
    }
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            //바다의 경우 다리 시작할 수 없음
            if(area[i][j] == 0)continue;
            
            for(int ii = 0; ii<N; ii++){
                for(int jj = 0; jj<N; jj++){
                    dist[ii][jj] = -1;
                }
            }
            
            int self = area[i][j];
            //육지에서 BFS
            queue<pair<int,int>> q;
            q.push({i,j});
            dist[i][j] = 0;
            while(!q.empty()){
                auto cur = q.front();
                q.pop();
                
                for(int dir = 0; dir<4; dir++){
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];
                    //범위 체크
                    if(nx < 0 || nx >= N || ny < 0 || ny >= N)continue;
                    //방문체크
                    if(dist[nx][ny] != -1)continue;
                    //자신과 같은 구역으로 다리를 놓지 않음.
                    if(area[nx][ny] == self)continue;
                    //자신과 같은 구역만 아니면 뻗어나감(바다, 다른 대륙)
                    
                    //다른 대륙이면
                    if(area[nx][ny] != 0){
                        minDist = min(minDist, dist[cur.X][cur.Y]);
                    }
                    //바다면
                    else{
                            dist[nx][ny] = dist[cur.X][cur.Y] + 1;
                            q.push({nx,ny});
                    }
                    
                }
            }
        }
    }
    
    cout << minDist << '\n';
    
    return 0;
}