https://www.acmicpc.net/problem/2146
2146번: 다리 만들기
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은, 섬들을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서
www.acmicpc.net
dfs와 bfs를 모두 활용한다.
dfs를 통해서 섬의 개수를 파악하고, 섬마다 index를 할당해준다.
이후에는 섬으로부터 바다로 탐색을 수행하고, 이때 bfs를 활용한다.
거리를 측정하기 시작한 섬에 대한 정보를 idx 배열에 저장해준다.
즉 i행 j열이 바다라고 한다면, 섬이 아니기 때문에 index가 할당되어있지 않은데,
어느 섬으로부터 측정한 거리라는 것을 idx 배열에 명시해준다.
이를 통해서 다른섬이 만났을 때, 그 지점까지의 거리가 만들 수 있는 다리의 최소 거리인지 판단해준다.
#include<iostream>
#include<queue>
using namespace std;
int m[100][100], n, dis[100][100], idx[100][100];
int dr[4] = { 0,0,1,-1 };
int dc[4] = { 1,-1,0,0 };
int Min = -2;
queue <pair<int, int> > q;
void init() {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dis[i][j] = -1;
while (!q.empty()) q.pop();
}
void minCal(int val) { //최소 거리인지 판단
if (Min == -2) { //최솟값이 갱신된 적이 없다면
Min = val;
return;
}
else {
if (Min > val) Min = val;
else
return;
}
}
bool boundCheck(int r, int c) {
return r < 0 || c < 0 || r >= n || c >= n;
}
void dfs(int row, int col, int landCnt) {
dis[row][col]++;
idx[row][col] = landCnt; //섬의 index 지정
for (int i = 0; i < 4; i++) {
int nr = row + dr[i];
int nc = col + dc[i];
if (boundCheck(nr, nc) || m[nr][nc] == 0 || dis[nr][nc] >= 0) continue;
dfs(nr, nc, landCnt);
}
}
void bfs(pair<int, int> start) {
q.push(start);
dis[start.first][start.second]++;
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int nr = cur.first + dr[i];
int nc = cur.second + dc[i];
if (boundCheck(nr, nc) || dis[nr][nc] >= 0) continue;
if (m[nr][nc] == 1) {
//섬을 만났을 때
if (idx[nr][nc] == idx[cur.first][cur.second]) continue;
else {
//출발한 섬과 다른 섬을 만났을 때
minCal(dis[cur.first][cur.second]);
init();
return;
}
}
q.push({ nr, nc });
dis[nr][nc] = dis[cur.first][cur.second] + 1;
idx[nr][nc] = idx[cur.first][cur.second];
//어느 섬에서 측정한 거리라는 것을 명시
}
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> m[i][j];
init();
int landCnt = 0; // 섬 번호
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dis[i][j] < 0 && m[i][j] == 1) {
landCnt++;
dfs(i, j, landCnt);
}
}
}
init(); //방문처리 배열 초기화
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dis[i][j] < 0 && m[i][j] == 1) {
bfs({ i, j });
}
}
}
cout << Min << '\n';
return 0;
}
//섬과 섬을 잇는 가장 짧은 다리
//1에서 시작해서 0으로 퍼져나가게
//퍼져나가기 시작한 점이 어느 섬인지 확인하면서 비교
//dfs로 섬 개수 파악하고 번호 매김
//섬이면서 방문 안 한 곳 bfs -> 주변이 바다인 곳 방문(거리측정)
//가다가 섬이면서 내 섬이 아닌 곳을 만나면 중지 -> 길이 최소 비교
'알고리즘 문제 풀이 > 백준 온라인 저지' 카테고리의 다른 글
| 백준 14499번: 주사위 굴리기 (C++) (0) | 2019.07.24 |
|---|---|
| 백준 1547번: 공 (C++) (0) | 2019.07.24 |
| 백준 1799번: 비숍 (C++) (0) | 2019.07.24 |
| 백준 15666번: N과 M (12) (C++) (0) | 2019.07.23 |
| 백준 15665번: N과 M (11) (C++) (0) | 2019.07.23 |