[BFS]백준 2146 다리만들기
업데이트:
백준 2146번
다리만들기
BFS를 사용해 해결할 수 있는 문제이다.
우선 BFS를 이용해 전체 지도에 있는 섬들을 분류해준다.
다만, 단순히 섬의 개수를 세는 것이 아니기 때문에 섬들을 각각 번호를 붙여서 저장한다.
첫 번째 섬은 1, 두 번째 섬은 2, 세 번째 섬은 3… 으로 저장한다.
여기까지가 준비 단계이다. 이제 섬들을 잇는 가장 짧은 다리의 길이를 구해야 한다.
이를 위해서는 모든 섬들을 확장하고 섬들끼리 만나는 순간을 포착해야 한다.
문제에서 주어진 예시는 다음과 같다.
10
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
각 섬들을 분류하면
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
섬들을 확장하기 위해서, 주변에 0이 있다면, 1로 채우는 과정을 반복해야 한다.
확장 1:
1 1 1 1 0 0 2 2 2 2
1 1 1 1 1 0 0 2 2 2
1 1 1 1 1 0 0 2 2 2
1 1 1 1 1 1 0 0 2 2
0 0 1 1 1 0 0 0 2 2
0 0 0 1 0 0 0 0 2 2
0 0 0 0 3 3 0 0 0 2
0 0 0 3 3 3 3 0 0 0
0 0 0 3 3 3 3 3 0 0
0 0 0 0 3 3 3 0 0 0
확장 2:
1 1 1 1 1 2 2 2 2 2
1 1 1 1 1 1 2 2 2 2
1 1 1 1 1 1 2 2 2 2
1 1 1 1 1 1 1 2 2 2
1 1 1 1 1 1 0 2 2 2
0 0 1 1 1 0 0 2 2 2
0 0 0 1 3 3 0 0 2 2
0 0 3 3 3 3 3 0 0 2
0 0 0 3 3 3 3 3 0 0
0 0 0 0 3 3 3 0 0 0
2 번의 확장에서 1 번과 3 번 섬이 연결된다.
이 때 다리의 길이는 두 번 확장한 1번 섬 (2) + 한 번 확장한 3번 섬 (1) = 3이다.
섬들이 만났을 때 다리의 길이를 계산하기 위해서는 추가로 배열을 가지고 있어야 한다.
처음 입력으로 주어진 섬들은 level 0 이라고 가정한다.
그리고, 확장되었을 때 각 좌표들은 자신이 몇 번째 확장에 생성된 것인지를 저장한다.
첫 번째 확장에 생성된 섬들은 level 1이다.
두 번째 확장에 생성된 섬들은 level 2이다.
가장자리에서 확장을 시도했을 때 0이 아니고, 다른 섬에 의해 이미 점령된 경우가 있다면 두 섬이 만난 것으로 판단한다.
두 섬이 만났을 때 각 섬의 level을 더하면 다리의 길이를 알 수 있다.
마지막까지 고생했던 반례는 다음과 같다.
5
1 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 0 0 1
정답 : 2
출력 : 3
계속해서 틀렸던 이유는, 지도의 위 쪽에서 먼저 섬들이 만나는 경우 바로 정답을 출력하고 종료했기 때문이다. 아래쪽에서 더 짧은 길이의 다리가 존재할 수 있다. 따라서, 섬들이 만나는 경우 해당 확장까지는 모두 확인한 뒤 가장 짧은 답을 출력하도록 수정하였더니 통과할 수 있었다.
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int x_iter[4] = {1,0,-1,0};
int y_iter[4] = {0,1,0,-1};
int main(){
int num;
std::cin >> num;
int map[101][101] = {0,};
bool visited[101][101] = {false,};
int id[101][101] = {0,};
int level[101][101] = {0,};
int group_id = 1;
// Map input
for(int i=0;i<num;i++){
for(int j=0;j<num;j++){
std::cin >> map[i][j];
}
}
// 섬 분류
vector<vector<pair<int,int> > > groups;
for(int i=0;i<num;i++){
for(int j=0;j<num;j++){
if(map[i][j] == 1 && visited[i][j] == false){
queue<pair<int,int> > q;
q.push(make_pair(i,j));
vector<pair<int,int> > tmp;
visited[i][j] = true;
while(!q.empty()){
pair<int,int> cur = q.front();
q.pop();
bool flag = true;
for(int k=0;k<4;k++){
int y = cur.first + y_iter[k];
int x = cur.second + x_iter[k];
if(y>=0 && y < num && x >=0 && x < num){
if(map[y][x] == 1 && visited[y][x]==false){
q.push(make_pair(y,x));
visited[y][x]=true;
id[y][x] = group_id;
}
else if(map[y][x]==0 && flag){
tmp.push_back(make_pair(cur.first,cur.second));
id[cur.first][cur.second] = group_id;
flag = false;
}
}
}
}
groups.push_back(tmp); // 가장자리만 들어있음.
group_id++;
}
}
}
// 섬 확장 && 만남 여부 확인
vector<int> answer;
while(1){
for(int i=0;i<groups.size();i++){
vector<pair<int,int> > tmp;
for(int j=0;j<groups[i].size();j++){
for(int k=0;k<4;k++){
int y = groups[i][j].first + y_iter[k];
int x = groups[i][j].second + x_iter[k];
if(y>=0 && y<num && x>=0 && x<num){
if(map[y][x]==0){
map[y][x] = 1;
id[y][x] = id[groups[i][j].first][groups[i][j].second];
tmp.push_back(make_pair(y,x));
level[y][x] = level[groups[i][j].first][groups[i][j].second] + 1;
}
else{
if(map[y][x]==1 && id[y][x] != id[groups[i][j].first][groups[i][j].second] && id[y][x]>0){
answer.push_back(level[y][x] + level[groups[i][j].first][groups[i][j].second]);
}
}
}
}
}
groups[i].clear();
groups[i] = tmp;
}
if(answer.size() != 0){
sort(answer.begin(), answer.end());
// cout << answer.size() << endl;
cout << answer[0];
return 0;
}
}
return 0;
}
댓글남기기