링크
https://www.acmicpc.net/problem/2146
문제
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.
이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.
위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.
물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나, 위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).
지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.
입력
첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다. 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.
출력
첫째 줄에 가장 짧은 다리의 길이를 출력한다.
풀이
#include <iostream>
#include <string>
#include<cstring>
#include <queue>
#include <vector>
using namespace std;
int n, Answer;
int map[100][100];
bool visit[100][100];
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
vector <pair <int, int>> v;
int Min(int A, int B) {
if (A < B)
return A;
return B;
}
void Input() {
Answer = 987654321;
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> map[i][j];
if (map[i][j] == 1) {
map[i][j] = -1; //나중에 각 칸에 해당하는 섬 라벨로 바꿀것임
v.push_back({ i,j });
}
}
}
}
void Make_LandLabel(int a, int b, int L) {
queue<pair<int, int>> q;
q.push({ a, b });
visit[a][b] = true;
map[a][b] = L; //map을 섬 라벨로 변경
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < n && ny < n) {
if (visit[nx][ny] == false && map[nx][ny] == -1) {
visit[nx][ny] = true;
map[nx][ny] = L;
q.push({ nx,ny });
}
}
}
}
}
int BFS(int Num) {
int Result = 0;
queue < pair<int, int>> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == Num) {
visit[i][j] = true;
q.push({ i,j }); //하나의 섬 칸을 모두 큐에 담는다.
}
}
}
while (!q.empty()) {
int S = q.size();
for (int i = 0; i < S; i++) { //현재 기준 큐 사이즈만큼 담긴거 전부 꺼낸다
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int j = 0; j < 4; j++) {
int nx = x + dx[j];
int ny = y + dy[j];
if (nx >= 0 && ny >= 0 && nx < n && ny < n) { //다른 섬 발견할 때까지 바다를 탐색.
if (map[nx][ny] != 0 && map[nx][ny] != Num) return Result;
//바다 칸이 아니면서 다른 섬 라벨을 만났다면 리턴
else if (map[nx][ny] == 0 && visit[nx][ny] == false) {
//바다 칸이면서 아직 방문하지않았다면
visit[nx][ny] = true;
q.push({ nx,ny });
}
}
}
}
Result++; //섬으로부터 같은 거리인 바다 칸들을 모두 push하고 Result(거리)값을 하나 올린다.
//다시 Queue 사이즈를 얻은다음에 bfs탐색해서 같은 Result(거리)값을 가진 칸들을 push반복.
}
}
void solution() {
int Land_Label = 1;
for (int i = 0; i < v.size(); i++) { //벡터에 담긴 모든 섬 칸들.
int x = v[i].first;
int y = v[i].second;
if (visit[x][y] == false) {
Make_LandLabel(x, y, Land_Label);
Land_Label++;
}
}
for (int i = 1; i < Land_Label; i++) {//라벨별로 bfs 탐색해서 다리 최소값 구하기
Answer = Min(Answer, BFS(i)); //맨첨에는 바다는 모두 visit false 상태다
memset(visit, false, sizeof(visit));
}
cout << Answer;
}
void solve() {
Input();
solution();
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
설명
오래 걸렸다.
섬이 아니라 바다도 탐색해야하는 유형은 처음이라 아이디어를 떠올리기 쉽지 않았다. 결국 블로그 풀이를 참고했다.
🤔 문제 풀기 전에 어떤 요구상항들이 있는지 명확하게 정리하고 코드를 짜야겠다.
👨🏻🏫 BFS 유형 중에 '시작점이 여러개인 BFS' 유형이다. -> 해결법 : 모든 시작점을 큐에 넣고 BFS를 돌리면 된다. 여기서 시작점은 바다 칸과 접하고 있는 테두리 칸이다. -> ⭐ BFS를 돌 때 큐에 쌓이는 순은 반드시 거리순이게 된다.
source : https://yabmoons.tistory.com/71
문제풀이
문제에서 해결해야 될 부분이 많은 것 같으니 해야될 내용을 정리해보자.
먼저, 서로 다른 대륙인지 같은 대륙인지 판단을 해야한다. 바다를 건넌다고 무조건 다른 대륙이 아니기 때문이다.
이런 경우, 대륙 가운데 바다가 있지만, 결국 하나의 대륙이기 때문에 같은 대륙인지 아닌지 확실히 판단하는 과정이 필요할 것이다.
두번째는 다리를 연결하되, 서로다른 대륙과 연결하는 다리를 연결해야 하며, 그 다리의 최소값을 구하는 과정이 있어야한다.
요약하면
1. 대륙간 번호 붙이기
2. 다리 연결하기
-
순서대로 해결해보자. 대륙간의 번호를 붙여보자. 이 과정을 위해서 처음 입력받을 때 육지를 1이 아닌 -1로 설정하였다. 왜냐하면 각 섬 칸에 대해서 대륙 1,2,3...이런 식으로 번호를 붙일 것이기 때문이다.
모든 대륙에서 bfs의 역할을 하는 함수를 호출해주면 된다.(함수 Make_LandLabel())
이 함수 안에서는 Queue를 이용해서 서로 인접해있으면서 아직 방문하지 않는 칸들의 번호를 넣어주면서 맵에서의 값을 동일한 섬 라벨을 붙여주면 된다. (이 과정은 흔한 bfs에서 떨어져 있는 시작점 찾는 문제처럼 이중 for문을 사용하면 간단하다.) -
다리를 연결하기에서는 (함수 BFS()) 먼저 BFS를 실행하기 전, 하나의 과정을 추가해주었다.
⭐🔥 같은 대륙에 있는 모든 땅들을 Queue에 넣고 시작하였다.
이후, BFS-Leveling Skill을 통해서 Queue의 Size만큼 진행을 하게 되는데,
이때 생각해야할 조건으로는
1. 맵의 범위내에 존재해야 한다.
2. 만약 이동하려는 칸이 바다라면 Queue에 넣어주고 계속 진행.(땅이 들어있는 Queue에서 나온 값이 바다와 붙어있는 테두리칸이겠지 -> 땅이 들어있는 Queue가 끝나면 같은 거리의 바다 칸을 pop하면서 bfs탐색한다. ⭐이때 거리는 +1해야겠지 왜냐하면 ⭐ BFS를 돌 때 큐에 쌓이는 순은 반드시 거리순이게 된다.)
3. 만약 이동하려는 칸이 육지이고 , 이동하기 전의 대륙의 번호와 다른 번호라면 종료
이 3가지 조건에 대해서만 구현을 하면된다.
이 조건들을 각 대륙에 대해서 , 즉 라벨링된 수만큼 반복해서 min을 찾는다.
