반응형

문제 링크:https://www.acmicpc.net/problem/2146

 

2146번: 다리 만들기

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

www.acmicpc.net

<문제 풀이> BFS

섬의 육지에서 시작해서 BFS로 다른 섬의 육지에 최초로 만나는 지점이 다리를 놓을 수 있는 방법 중에 하나입니다.

그래서 문제를 해결하기 위해서

1. bfs로 섬을 구분한다. 

10
1 1 1 0 0 0 0 2 2 2
1 1 1 1 0 0 0 0 2 2
1 0 1 1 0 0 0 0 2 2
0 0 1 1 1 0 0 0 0 2
0 0 0 1 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
0 0 0 0 3 3 0 0 0 0
0 0 0 0 3 3 3 0 0 0
0 0 0 0 0 0 0 0 0 0

2. i번째 섬의 모든 육지를 큐에 담고 최초로 다른 섬과 만날 때까지 최단거리를 갱신한다.

-> 모든 섬에 대해서 bfs를 돌리고 최솟값을 구하면 됩니다. 

 

<C++ 소스 코드>

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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
#define X first
#define Y second
 
int board[100][100];
int visited1[100][100]; // 섬 구분
int visited2[100][100]; // 최단 거리
int dx[4= { 010-1 };
int dy[4= { 1 , 0-10 };
 
int n;
int flag = 1;
int res = INT_MAX;
 
void bfs1() {// 섬 구분
    queue<pair<intint> > Q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 1 && !visited1[i][j]) {
                Q.push({ i, j });
                visited1[i][j] = true;
                board[i][j] = flag;
                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 || ny < 0 || nx >= n || ny >= n)continue;
                        if (board[nx][ny] != 1 || visited1[nx][ny])continue;
                        Q.push({ nx, ny });
                        board[nx][ny] = flag;
                        visited1[nx][ny] = true;
                    }
                }
                flag++;
            }
        }
    }
    flag--;
}
 
void bfs2() { //최단거리
    flag = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == flag) {
                queue<pair<intint> > Q;
                Q.push({ i, j });
                visited2[i][j] = 1;
                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 || ny < 0 || nx >= n || ny >= n)continue;
                        if (visited2[nx][ny] && visited2[nx][ny] <= visited2[cur.X][cur.Y] + 1)continue;
                        if (board[nx][ny] == flag) {
                            visited2[nx][ny] = 1;
                            Q.push({ nx, ny });
                        }
                        else if (board[nx][ny] == 0) {
                            visited2[nx][ny] = visited2[cur.X][cur.Y] + 1;
                            Q.push({ nx, ny });
 
                        }
                        else if (board[nx][ny] != flag) {
                            res = min(res, visited2[cur.X][cur.Y] - 1);
                          
                        }
                    }
                }
                flag++;
                fill(&visited2[0][0], &visited2[99][100], 0);
            }
        }
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }
    bfs1();
    bfs2();
    cout << res;
    return 0;
}
 
cs

 

반응형

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 6593번] 상범 빌딩  (0) 2021.11.19
[백준 5014번] 스타트링크  (0) 2021.11.19
[백준 5427번] 불  (0) 2021.11.17
[백준 7562번] 나이트의 이동  (0) 2021.11.16
[백준 10026번] 적록색약  (0) 2021.11.05

+ Recent posts