[백준OJ] 5547번 일루미네이션

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

5547번: 일루미네이션

---

 

풀이

기본적으로 BFS를 이용하여 문제를 해결할 것이다.

건물을 BFS로 돌면서, 외벽의 개수를 세어주면 되는 일인데, 여기서 외벽인지 내벽인지 판별하는것이 가장 큰 문제이다.

 

여러 풀이방법이 있겠지만, 건물에 대한 BFS를 돌기전에, 건물이 지어지지 않은 공간을 먼저 BFS를 돌며, 만약 외부( 범위 밖) 과 접촉한 건물이 없는 공간이라면, 이 비어있는 공간들은 모두 외부이다. 만약 BFS를 돌면서 범위 밖으로 넘어가지 못하는 공간이라면, 그 공간은 내부이다.

 

위의 공간에서, (1,1)과 (1,2)는 BFS를 돌면 범위 바깥과 접촉한다는것을 알 수 있으므로, 저 둘은 외부이다.

(2,3)을 보면, BFS를 전부 돌려도 범위 밖과 접촉을 하지 못하므로 내부공간이라 할 수 있다.

위와같이 범위 밖, 혹은 밖으로 갈 수 있는 공간을 외부라고 지정을 해놓은 뒤, 건물에 대한 BFS를 돌면서, 외부에 접촉한 부분을 만나면 ANSWER++를 해주면 된다.

 

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

typedef pair<int, int> pii;

int maze[101][101] = { 0 };
int mv[2][6][2] = { 
	{ {-1,-1},{0,-1},{1,0},{0,1},{-1,1},{-1,0} },
	{ {0,-1},{1,-1},{1,0},{1,1},{0,1},{-1,0} } 
};
int w, h;

bool isIn(int x, int y) {
	return 1 <= x && x <= w && 1 <= y && y <= h;
}

void make_outside() {
	bool visited[101][101] = { 0 };
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			if (maze[j][i] == 0 && !visited[j][i]) {
				queue<pii> q;
				vector<pii> v;
				q.push({ j,i });
				visited[j][i] = true;
				bool flag = false;
				while (!q.empty()) {
					int x = q.front().first;
					int y = q.front().second;
					q.pop();
					v.push_back({ x,y });

					for (int d = 0; d < 6; d++) {
						int line = y % 2;
						int nx = x + mv[line][d][0];
						int ny = y + mv[line][d][1];
						if (!isIn(nx, ny)) {
							flag = true;
						}
						else {
							if (maze[nx][ny] == 0 && !visited[nx][ny]) {
								q.push({ nx,ny });
								visited[nx][ny] = true;
							}
						}
					}
				}
				if (flag) {
					for (pii out : v) {
						int x = out.first;
						int y = out.second;
						maze[x][y] = -1;
					}
				}
			}
		}
	}
}

int bfs() {
	int answer = 0;
	bool visited[101][101] = { 0 };

	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			if (maze[j][i] == 1&&!visited[j][i]) {
				queue<pii> q;
				q.push({ j,i });
				visited[j][i] = true;
				while (!q.empty()) {
					int x = q.front().first;
					int y = q.front().second;
					q.pop();
					for (int d = 0; d < 6; d++) {
						int line = y % 2;
						int nx = x + mv[line][d][0];
						int ny = y + mv[line][d][1];
						if (!isIn(nx, ny)) {
							answer++;
						}
						else {
							if (maze[nx][ny] == 1&& !visited[j][i]) {
								q.push({ nx,ny });
								visited[nx][ny] = true;
							}
							else if (maze[nx][ny] == -1) {
								answer++;
							}
						}
					}
				}
			}
		}
	}
	return answer;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> w >> h;
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cin >> maze[j][i];
		}
	}
	make_outside();

	cout << bfs() << "\n";
}