코딩공작소
[백준]다리만들기 본문
https://www.acmicpc.net/problem/2146
2146번: 다리 만들기
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은, 섬들을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서
www.acmicpc.net
흠 .. A형문제랑 살짝비슷(좀더 쉬움) .. 섬별로 단지인덱싱을 하고 섬별로 출발을 해서 최소 거리를 구하는..?
배울게 많은 문제.!
|
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
|
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct INFO {
int r,c;
};
int N, ans = 1e9;
int map[100][100], dis[100][100];
bool isV[100][100];
queue<INFO> q;
int dr[] = { 0,0,-1,1 }, dc[] = { 1,-1,0,0 };
int cnt = 1;
void dfs(int r, int c) {
isV[r][c] = true;
map[r][c] = cnt;
for (int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
if (!isV[nr][nc] && map[nr][nc]) dfs(nr, nc);
}
}
void bfs(int k) {
memset(dis, -1, sizeof(dis)); //초기화
for (int i = 0; i < N; i++) { //시작점 push
for (int j = 0; j < N; j++) {
if (map[i][j] == k) {
q.push({ i,j });
dis[i][j] = 0;
}
}
}
while (!q.empty()) {
int r = q.front().r, c = q.front().c; q.pop();
for (int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
if (!map[nr][nc] && dis[nr][nc] == -1) {
//방문안한점. 거리늘려가며 대입
q.push({ nr,nc });
dis[nr][nc] = dis[r][c] + 1;
}
if (map[nr][nc] && map[nr][nc] != k) { //어딘가의 단지에 닿았을 때
if (ans >= dis[r][c]) ans = dis[r][c];
while (!q.empty()) q.pop(); //q비워주기
return;
}
}
}
}
void solve() {
//단지 번호붙이기 느낌.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!isV[i][j] && map[i][j]) {
dfs(i, j);
cnt++;
}
}
}
//각 단지마다 출발해서 bfs로 거리측정.
for (int i = 1; i <= cnt; i++) {
bfs(i);
}
printf("%d\n", ans);
}
int main()
{
cin >> N;
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> map[i][j];
solve();
return 0;
}
|
cs |
'알고리즘 > 그래프' 카테고리의 다른 글
| [백준]PuyoPuyo (0) | 2019.09.15 |
|---|---|
| [백준]섬의개수 (0) | 2019.09.14 |
| [백준]단지번호붙이기 (0) | 2019.09.14 |
| 섬번호매기기 (0) | 2019.09.13 |
| [백준]연구소2 (0) | 2019.09.03 |