2146 - 다리만들기 - BFS
문제
문제링크 : https://www.acmicpc.net/problem/2146
풀이전략
- 섬과 섬을 연결한다는 것을 알기 위해, 섬과 섬을 구별해야한다. 따라서 먼저 각 영역을 분리해주었다.
- N은 100이하이고 각 영역당 계산의 최대값은 N^2이므로 최대 N^2개의 영역이기 때문에 N^4이 되어도 시간은 충분하였기 때문에 다 찾아보았다.
- 영역마다 이어질때까지 BFS로 찾았다.
- 체크배열을 만들어 중복되는 부분은 방문하지 않았다.
코드
#include<bits/stdc++.h>
using namespace std;
int N;
int mp[102][102];
bool ch[102][102];
int territoryCnt = 0;
int territoryColor = 2;
int territoryStart = 2;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
struct road{
int r, c, dis;
road(int aa, int bb, int cc){
r = aa;
c = bb;
dis = cc;
}
};
// 영역을 구별해주는 함수이다. DFS로 구현하였다.
void findTerritory(int r, int c, int color){
for(int i=0; i<4; i++){
int rr = r+dy[i];
int cc = c+dx[i];
if(!ch[rr][cc] && mp[rr][cc] == 1){
ch[rr][cc] = true;
mp[rr][cc] = color;
findTerritory(rr,cc,color);
}
}
}
// 각 영역마다 다른 대륙을 이으는 최소값을 구하는 것이다.
int findRoadLength(int r, int c, int color){
queue<road> q;
q.push(road(r,c,0));
ch[r][c] = true;
// 먼저 해당위치에 값을 큐에 넣어준다.
while(!q.empty()){
road ret = q.front();
q.pop();
// 이동을 하며 찾되, 자기와 같은 색이 아니고 바다이거나 다른 대육일 떄 이동한다.
for(int i=0; i<4; i++){
int rr = ret.r+dy[i];
int cc = ret.c+dx[i];
// 바다가 아닌 다른 대륙일 경우 리턴해준다.
if(!ch[rr][cc] && mp[rr][cc] != 0 && mp[rr][cc] != color){
return ret.dis;
}
// 바다일경우 다시 queue에 넣어준다.
else if(!ch[rr][cc] && mp[rr][cc] == 0 && rr > 0 && rr <= N && cc > 0 && cc<=N){
ch[rr][cc] =true;
q.push(road(rr,cc,ret.dis+1));
}
}
}
return 2147000000;
}
int main(){
ios_base::sync_with_stdio(false);
// freopen("../input.txt","rt",stdin);
cin >> N ;
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
cin >> mp[i][j];
}
}
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
if(mp[i][j] == 1){
memset(ch, false, sizeof(ch));
ch[i][j] = true;
mp[i][j] = territoryColor;
findTerritory(i, j, territoryColor);
territoryColor++;
territoryCnt++;
}
}
}
int res = 2147000000;
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
if(mp[i][j] != 0){
memset(ch, false, sizeof(ch));
res = min(res,findRoadLength(i, j, mp[i][j]));
}
}
}
cout<<res<<endl;
return 0;
}
소감
DFS와 BFS를 같이 조합시키는 재미있는 문제였다. 시간복잡도를 잘 계산할 수 있다면 충분히 완전탐색을 해도 괜찮은 문제임을 알수있다. 대륙의 한 부분마다 따로따로 BFS를 해준 부분이 매우 좋은 아이디어이다.
Author And Source
이 문제에 관하여(2146 - 다리만들기 - BFS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gomster_96/백준-2146-다리만들기-BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)