취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 5547번 문제인 일루미네이션이다.
문제는 아래 링크를 확인하자.

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

주어진 그림에 각 육각형을 좌우로 나누는 세로방향의 대각선을 모두 긋고, 그 결과 나오는 사각형들을 정사각형 모양으로 모양을 변형시켜보자.

위와 같은 변형을 했다면 이제 평범한 사각격자에서의 도형의 둘레를 구하는 문제를 풀면 된다!

사각격자에서의 1로 이루어진 도형의 둘레는 1. 바깥에 해당하는 칸을 모두 채우고 2. 바깥이 아닌 칸들을 바깥이 아니라 표기한 다음 3. 도형에 해당하는 각 칸의 상하좌우를 살펴 바깥과 접하는 면의 개수를 세는 것으로 구할 수 있다.

아래는 제출한 소스코드이다.

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

int R, C;
int RR, CC;
int arr[102][203];
int dr[4] = { 1,-1,0,0 };
int dc[4] = { 0,0,1,-1 };

void bfs() {
	arr[0][0] = -1;
	queue<pair<int, int>> que;
	que.push(make_pair(0, 0));
	
	while (!que.empty()) {
		int r = que.front().first, c = que.front().second; que.pop();
		for (int i = 0; i < 4; i++) {
			int rr = r + dr[i], cc = c + dc[i];
			if (rr<0 || rr>RR || cc<0 || cc>CC) continue;
			if (arr[rr][cc]) continue;
			arr[rr][cc] = -1;
			que.push(make_pair(rr, cc));
		}
	}
}

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

	cin >> C >> R;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			int x; cin >> x;
			if (x) {
				if (r & 1) arr[r][2 * c] = arr[r][c * 2 + 1] = 1;
				else arr[r][2 * c - 1] = arr[r][c * 2] = 1;
			}
		}
	}

	RR = R + 1, CC = 2 * C + 2;
	
	bfs();

	for (int r = 0; r <= RR; r++) {
		for (int c = 0; c <= CC; c++) {
			if (arr[r][c] == 0) arr[r][c] = 1;
		}
	}

	int ans = 0;
	for (int r = 1; r < RR; r++) {
		for (int c = 1; c < CC; c++) {
			if (arr[r][c] == 1) {
				for (int i = 0; i < 4; i++) {
					if (arr[r + dr[i]][c + dc[i]] == -1) ans++;
				}
			}
		}
	}

	cout << ans;
}