백준 C++ 2234번

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

 

이 문제에서 비트가 켜져있으면 이동하면 안된다라는 점은 쉽게 알아낼 수 있었다.

하지만 고민한 문제는 벽을 1개를 허문다는 점이었다.

실제로 모든 칸에 대해서 한 비트씩 끄는 건 너무 비효율적이라고 생각했어서 다른 방법을 찾았어야했다.

생각보다 방법은 쉽게 할 수 있었는데 visited로 구역을 나누는 것으로 했다.

 

#include <iostream>

using namespace std;

//성 방의 갯수 ->  sectionNum - 1
//가장 넓은 방의 넓이
//하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기

int n, m; int sectionSize = 0;
int sectionNum = 0;
int maxSectionSize = 0;
int maxLinkSectionSize = 0;

int castle[51][51];
int visited[51][51];
int sections[55];
int dy[] = { 0, -1, 0, 1 };			//비트에 알맞게 순서가 바뀐것을 확인할 수 있다.
int dx[] = { -1, 0, 1, 0 };

void dfs(int y, int x, int sectionNum)
{
	visited[y][x] = sectionNum;
	sectionSize += 1;
	for (int i = 0; i < 4; i++) {
		if (castle[y][x] & (1 << i)) continue;		//castle과 i번째의 비트를 비교해서 1이면(비트가 켜져있으면 )벽이 있기에 갈 수 없다.

		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;

		dfs(ny, nx, sectionNum);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> m >> n;

	fill(&visited[0][0], &visited[0][0] + 51 * 51, 0);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int t; cin >> t;
			castle[i][j] = t;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visited[i][j]) continue;
			//cout << "i : " << i << "    j : " << j << '\n';			//dfs 시작점 출력
			sectionSize = 0; sectionNum += 1;
			dfs(i, j, sectionNum);
			
			maxSectionSize = max(maxSectionSize, sectionSize);
			sections[sectionNum] = sectionSize;
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (j + 1 < m) {
				if (visited[i][j] != visited[i][j + 1]) {		//우측의 섹션이 다른 넘버라면
					maxLinkSectionSize = max(maxLinkSectionSize, sections[visited[i][j]] + sections[visited[i][j + 1]]);
				}
			}

			if (i + 1 < n) {
				if (visited[i][j] != visited[i + 1][j]) {		//아래쪽의 섹션이 다른 넘버라면
					maxLinkSectionSize = max(maxLinkSectionSize, sections[visited[i][j]] + sections[visited[i+1][j]]);
				}
			}
		}
	}

	cout << sectionNum<< "\n";
	cout << maxSectionSize << "\n";
	cout << maxLinkSectionSize << "\n";

}