Algorithm/BOJ

[백준 2146] 다리만들기 C++

Henu 2021. 5. 22. 23:37
 

2146번: 다리 만들기

여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다

www.acmicpc.net

그래프 탐색, BFS

삼성전자 A형 기출문제

1. 문제풀이 아이디어

각 섬을 BFS로 돌면서 해당 섬의 경계좌표를 찾아서 저장한다

섬 간의 거리(경계좌표간의 거리)를 모두 찾아보면서 최솟값을 구한다

2. 코드 설명

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <vector>
#include <queue>
#define INF 1e9+7
using namespace std;
 
struct point{
    int r, c;
};
 
int N, Map[101][101];
int dr[4] = {0, 0, 1, -1}, dc[4] = {1, -1, 0, 0};
bool visited[101][101];
 
vector< vector<point> > boundary;
 
void input(){
    cin >> N;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> Map[i][j];
        }
    }
}
 
// 섬을 탐색하며 현재 섬의 경계를 찾아냄
void island_boundary(int r, int c){
    vector<point> land;     // 현재 섬의 경계를 저장하는 배열
    queue<point> que;       // 현재 탐색중인 섬
    que.push({r, c});
    
    visited[r][c] = true;
    
    while(!que.empty()){
        point now = que.front();
        que.pop();
        
        // 현재 좌표가 섬의 경계좌표인지 확인
        for(int i = 0; i < 4; i++){
            int nr = now.r + dr[i];
            int nc = now.c + dc[i];
            if(nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
            if(Map[nr][nc] == 0){
                land.push_back({now.r, now.c});
                break;
            }
        }
        
        // 현재 섬의 다른 육지부분을 que에 넣어준다
        for(int i = 0; i < 4; i++){
            int nr = now.r + dr[i];
            int nc = now.c + dc[i];
            if(nr < 0 || nr >= N || nc < 0 || nc >= N || visited[nr][nc] || !Map[nr][nc]) continue;
            
            visited[nr][nc] = true;
            que.push({nr, nc});
        }
    }
    
    boundary.push_back(land);
}
 
// 좌표간의 거리를 반환
int dist(point &a, point &b){
    return abs(a.r - b.r) + abs(a.c - b.c) - 1;
}
 
//a섬과 b섬의 경계를 돌면서 최소거리를 반환
int min_dist(vector<point> &a, vector<point> &b){
    int min_d = INF;
    for(int i = 0; i < a.size(); i++){
        for(int j = 0; j < b.size(); j++){
            min_d = min(min_d, dist(a[i], b[j]));
        }
    }
    return min_d;
}
 
void solve(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(Map[i][j] == 1 && !visited[i][j]){
                island_boundary(i, j);
            }
        }
    }
    
    int result = INF;
    
    // 섬간의 거리를 모두 탐색
    for(int i = 0; i < boundary.size()-1; i++){
        for(int j = i+1; j < boundary.size(); j++){
            // 섬간의 거리중 최솟값 반환
            result = min(result, min_dist(boundary[i], boundary[j]));
        }
    }
    
    cout << result;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve();
    
    return 0;
}
 
 cs