https://www.acmicpc.net/problem/2146
2146번: 다리 만들기
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다
www.acmicpc.net
문제접근 및 풀이
기본적으로 BFS로 접근했다.
2개의 섬만을 잇는 최단경로를 구해야 하므로 바다와 인접한 칸(테두리 칸이라고 하겠다)들을 구별했다.
그 후 테두리칸들에 대해 서로 bfs를 진행하면서 최단경로를 구하는 방식으로 해결했다.
step1 : 테두리 칸에 번호부여하기
- 부여받은 인풋배열 b[][]를 돌면서 각 섬에 대해 인덱싱(v[][])을 진행한다. 이때 바다와 인접하지 않은 지역은 -1로 설정해준다.
- 섬마다 테두리칸들을 구별해야 하므로 1,2,3,...이런식으로 증가하는 인덱스값을 부여해주었다.
step2 : 각 테두리 칸에 대해 BFS탐색하여 다른섬으로 가는 최단경로 탐색하기
- 테두리칸들에 대해 서로 bfs를 진행한다.
- 인덱싱한 값을 매게변수로 넘겨주어서 같은 섬의 테두리는 탐색하지 않도록 한다.
- 바다인 칸 혹은 다른 섬의 테두리만 탐색한다.
#include <iostream>
#include <queue>
#include <algorithm>
#define MAX 100
using namespace std;
int n,key=1, result=987654321;
int b[MAX][MAX]={0};
int v[MAX][MAX]={0};
int k[MAX][MAX]={0};
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
void bfs(int i, int j, int key){
queue<pair<int,int>> q;
q.push({i,j});
v[i][j]=1;
while(!q.empty()){
int find=0;
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(v[nx][ny]==0 && b[nx][ny]==1){
v[nx][ny]=1;
q.push({nx,ny});
}
if(b[nx][ny]==0){//b = 0 바다라면
k[x][y] = key;
find=1;
}
}
}
if(find==0){
k[x][y]=-1;
}
}
return ;
}
void bfs2(int i, int j, int key){
//탐색조건 k[][] 가 -1(육지) 혹은 key(같은 테두리)가 아니라면 탐색
int v[MAX][MAX]={0};
queue<pair<pair<int,int>, int>> q;
q.push({{i,j},0});
v[i][j]=1;
while(!q.empty()){
int x = q.front().first.first;
int y = q.front().first.second;
int c = q.front().second;
q.pop();
if(k[x][y]!=0 && k[x][y]!=key){
result = min(result, c);
return ;
}
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(v[nx][ny]==0 && k[nx][ny]>=0 && k[nx][ny]!=key){ // 메모리초과 -> v체크안했었음
v[nx][ny] = 1;
q.push({{nx,ny}, c+1});
}
}
}
}
return ;
}
int main()
{
cin >> n;
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
scanf("%d", &b[i][j]);
}
}
//step1 : 테두리 번호 부여하기
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(b[i][j]==1 && v[i][j]==0){
bfs(i,j,key);
key++;
}
}
}
//step2 : 각 테두리 칸에 대해 bfs하여 다른 테두리 카능로 가는 최단거리 탐색
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
int key = k[i][j];
if(key > 0){ // key가 0보다 크다면 번호가 부여된 테두리이다.
bfs2(i,j,key);
}
}
}
cout << result-1;
return 0;
}
느낀점
- 생각보다는 간단하게 해결되는 문제이지만 생각을 충분히 한 후에 단박에 풀어낼 수 있어서 뿌듯했다.
'알고리즘 문제풀이' 카테고리의 다른 글
[백준] 2475번 검증수 c++ (0) | 2022.02.04 |
---|---|
[백준] 1074번 Z c++ (0) | 2022.01.25 |
[백준] 15663 N과 M (9) c++ (0) | 2021.09.04 |
[백준] 15665번 N과 M (11) c++ (0) | 2021.09.04 |
[백준] 20040번 사이클 게임 c++ (0) | 2021.08.30 |