성곽
[Gold III] 성곽 - 2234Permalink
성능 요약Permalink
메모리: 2052 KB, 시간: 0 ms
분류Permalink
너비 우선 탐색, 비트마스킹, 그래프 이론, 그래프 탐색
제출 일자Permalink
2024년 7월 11일 23:05:02
문제 설명Permalink
대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오.
- 이 성에 있는 방의 개수
- 가장 넓은 방의 넓이
- 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기
위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다.
성은 M × N(1 ≤ M, N ≤ 50)개의 정사각형 칸으로 이루어진다. 성에는 최소 두 개의 방이 있어서, 항상 하나의 벽을 제거하여 두 방을 합치는 경우가 있다.
입력Permalink
첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다. 참고로 이진수의 각 비트를 생각하면 쉽다. 따라서 이 값은 0부터 15까지의 범위 안에 있다.
출력Permalink
첫째 줄에 1의 답을, 둘째 줄에 2의 답을, 셋째 줄에 3의 답을 출력한다.
비트 마스킹은 그냥 명시적으로 사용하라 해서 문제가 되지 않음
그러나, Connected Component를 이용해야 하는 것을 파악하지 못해 고생을 좀 했음
이번 기회에 Connected Component를 DFS로 푸는것 숙지해야 할 듯
나머지 로직은 뻔하므로 설명 생략
#include <iostream>
using namespace std;
int M,N;
int visited[51][51],map[51][51];
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int roomSize[2501];
int groupNum;
int maxRoomSize;
int crashedMaxRoomSize;
void go(int y,int x,int group){
// visiting process
visited[y][x]=group;
roomSize[group]++;
// bruching & pruning process
for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
if(!((map[y][x]>>i)&1)&&!visited[ny][nx]) go(ny,nx,group);
}
}
int main(){
//init
cin>>N>>M;
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
cin>>map[i][j];
}
}
//dfs
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
if(!visited[i][j]){
go(i,j,++groupNum);;
}
}
}
for(int i=1;roomSize[i];i++) maxRoomSize=max(roomSize[i],maxRoomSize);
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
if(i+1<M){
int currentGroup=visited[i][j];
int nextGroup=visited[i+1][j];
if(currentGroup!=nextGroup) crashedMaxRoomSize=max(crashedMaxRoomSize,roomSize[currentGroup]+roomSize[nextGroup]);
}
if(j+1<N){
int currentGroup=visited[i][j];
int nextGroup=visited[i][j+1];
if(currentGroup!=nextGroup) crashedMaxRoomSize=max(crashedMaxRoomSize,roomSize[currentGroup]+roomSize[nextGroup]);
}
}
}
cout<<groupNum<<endl;
cout<<maxRoomSize<<endl;
cout<<crashedMaxRoomSize<<endl;
return 0;
}
Leave a comment