[백준] 5547 - 일루미네이션

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

5547번: 일루미네이션

 

벌집 같은 구조의 판에서 이어져있는 집을 판별하고, 집의 외부와 내부를 판별해야 하는 문제였다.

 

먼저 이어져있는 집을 판별해보자.

 

이부분은 dfs나 bfs를 사용하면 된다.

다만, 일반적인 형태의 dx, dy 테크닉을 사용하면 어딘가에서 오류가 날 것이다.

 

문제를 잘 보면, 아래와 같이 y좌표가 홀수인지, 짝수인지에 따라서 x좌표의 dx가 달라진다.

 

 

따라서 홀수일 때 dy를 적용할 oddy, 짝수일 때 dy를 적용할 eveny를 따로 설정해주었다.

실제로 구현할 때는 배열을 사용하기 편하게 x, y의 위치를 바꾸어 주었다.

 

 

다음은 외부, 내부 판별이다.

이 부분은 상하좌우 바깥에 한 줄씩 추가에서, (0, 0)에서 bfs를 한 번 더 돌려주었다. 그렇게 하면 bfs 한 번으로 모든 외부를 찾을 것이고, 집이 아닌 곳인데도 내부를 판별할 수 있다.

 

이 과정이 끝났으면 모든 집들을 탐색하며 인접한 좌표가 외부일 때 조명을 장식한다고 볼 수 있겠다.

 

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

int w, h, map[102][102], visit[102][102], outside[102][102];

//오른쪽 부터 시계방향으로
int x[6] = { 0,1,1,0,-1,-1 };
int oddy[6] = { 1,1,0,-1,0,1 }; //홀
int eveny[6] = { 1,0,-1,-1,-1,0 };

bool ok(int nx, int ny) {
	return nx > 0 && ny > 0 && nx <= h && ny <= w;
}

int main() {

	cin >> w >> h;

	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cin >> map[i][j];
		}
	}

	int ans = 0;

	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			if (map[i][j] == 1 && !visit[i][j]) {

				queue<pair<int, int>> q;
				q.push({ i,j });
				visit[i][j] = 1;

				while (!q.empty()) {
					int a = q.front().first;
					int b = q.front().second;
					q.pop();

					for (int k = 0; k < 6; k++) {
						int nx = a + x[k];
						int ny;
						if (a % 2 == 0)ny = b + eveny[k];
						else ny = b + oddy[k];

						if (ok(nx, ny) && map[nx][ny] && !visit[nx][ny]) {
							visit[nx][ny] = 1;
							q.push({ nx,ny });
						}

					}
				}
			}
		}
	}

	queue<pair<int, int>> q;
	q.push({ 0,0 });
	outside[0][0] = 1;

	while (!q.empty()) {
		int a = q.front().first;
		int b = q.front().second;
		q.pop();

		for (int k = 0; k < 6; k++) {
			int nx = a + x[k];
			int ny;
			if (a % 2 == 0)ny = b + eveny[k];
			else ny = b + oddy[k];

			if (nx >= 0 && nx <= h + 1 && ny >= 0 && ny <= w + 1 && !map[nx][ny] && !outside[nx][ny]) {
				outside[nx][ny] = 1;
				q.push({ nx,ny });
			}
		}
	}

	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			if (map[i][j]) {
				for (int k = 0; k < 6; k++) {
					int nx = i + x[k];
					int ny;
					if (i % 2 == 0)ny = j + eveny[k];
					else ny = j + oddy[k];

					if (outside[nx][ny])ans++;
				}
			}
		}
	}

	cout << ans;

	return 0;
}