[백준] 2234번 성곽 (C++)

https://www.acmicpc.net/problem/2234

 

문제 설명

 

m*n 형태의 숫자를 입력을 받는다.

각 숫자는 0에서 15 사이의 숫자로 구성되어 있고, 이 숫자는 벽의 위치를 나타낸다.

서쪽에 벽이 있을때 1, 북쪽 에 벽이 있을때 2, 동쪽 에 벽이 있을때 4, 남쪽 에 벽이 있을때 8이 더해져있다.

이 성에 있는 방의 개수, 가장 넓은 방의 크기, 하나 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 구하면 된다.

주요 로직

1. dfs를 사용해 방의 개수와 각 방의 넓이를 구한다.

-> 입력 받은 숫자를 비트마스킹을 통해 벽이 있는 곳은 탐색하지 못하도록 구현한다. 

2. 벽 하나를 제거했을 때 얻을 수 있는 가장 넓은 방의 크기를 찾는다.

-> visited[][] 배열에 단순히 1,0 으로 방문 여부를 표현하는 것이 아니라 방별로 다른 수를 부여해 완전탐색을 통해 제거할 벽을 찾는다.

정답 코드

 

#include <bits/stdc++.h>

using namespace std;

int n,m,cnt;
int arr[53][53], visited[53][53];
int dy[4] = {0,-1,0,1}, dx[4] = {-1,0,1,0};
vector<int> v, v_mx;

int dfs(int y, int x){
	int ret = 1;
	visited[y][x] = cnt;
	for(int i=0; i<4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
		if(visited[ny][nx]) continue;
		if(arr[y][x] & (1<<i)) continue;
		ret += dfs(ny,nx);
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> m >> n;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cin >> arr[i][j];
		}
	}
	
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(visited[i][j] == false){
				cnt++;
				int val = dfs(i,j);
				v.push_back(val);
			}
		}
	}
	
	for(int i=0; i<n; i++){
		for(int j=0; j<m-1; j++){
			if(visited[i][j] != visited[i][j+1]){
				int cnt = v[visited[i][j]-1] + v[visited[i][j+1]-1];
				v_mx.push_back(cnt);
			}
		}
	}
		
	for(int i=0; i<m; i++){
		for(int j=0; j<n-1; j++){
			if(visited[j][i] != visited[j+1][i]){
				int cnt = v[visited[j][i]-1] + v[visited[j+1][i]-1];
				v_mx.push_back(cnt);
			}
		}
	}

	sort(v.begin(), v.end());
	sort(v_mx.begin(), v_mx.end());
	cout << v.size() << "\n" << v[v.size()-1] << "\n";
	cout << v_mx[v_mx.size()-1] << "\n";
	return 0;
}