[C++] 백준 10026번: 적록색약

문제 바로가기

---

문제

크기가 N×N인 그리드의 각 칸에 RGB 중 하나를 칠한 그림이 있다.

같은 색으로 이루어져 있는 구역으로 몇 개 나뉘어져 있다.

같은 색상이 상하좌우로 인접해 있으면 같은 구역에 속한다.

적록색약인 사람은 R과 G를 구별하지 못 한다.

그리드가 주어졌을 때, 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역수를 세어보자.

 

---

조건

1 ≤ N ≤ 100

 

---

풀이

이 문제는 2667번의 응용버전이다.

그리드에서 RGB 문자가 있는 한 칸을 기준으로 너비우선탐색을 하는데, 한 번 방문한 칸에는 숫자 등을 채워 넣는다.

그리고 더 이상 RGB 문자가 등장하지 않을 때까지 이를 반복한 뒤, 몇 번을 반복했는지만 출력하면 그게 구역의 수이다.

이 문제에서는 이를 두 번 반복해야 하는데, 왜냐하면 R과 G를 같다고 가정하는 적록색약의 경우를 별도로 고려해줘야 하기 때문이다.

따라서, 각 탐색을 시작할 때, 그리드의 정보를 다른 임시 그리드에 복사하여 그 임시 그리드를 가지고 너비우선탐색을 반복해야 한다.

아래는 프로그램의 동작과정이다.

 

1. 우선, grid의 정보를 입력받아 저장한다.

2. grid를 _grid에 복사한다.

3. 구역의 수를 나타낼 변수 count를 선언하고 초기값을 0으로 둔다.

4. 그리고 아래(5 ~ 8)를 반복한다.

  5. _grid에서 RGB 문자가 있는 칸을 찾고, 그 위치를 큐 BFS에 담은 뒤 지정한 레이블로 이동한다.

    - 이 때 그 칸의 색을 color 변수에 저장한다.

  6. 만약, RGB 문자가 있는 칸을 찾지 못 했다면 반복을 탈출한다.

  7. 너비우선탐색을 진행한다. 인접한 칸이 color와 같은 색이라면 BFS에 넣는다.

  8. 방문한 칸에는 count의 값을 저장한다.

  9. count의 값에 1을 더한다.

10. 위의 과정 중 2 ~ 9를 한 번 더 반복하는데, 이 때는 2의 과정에서 R과 G는 한 문자로 통일한다.

 

📕 코드보기(틀린 코드)

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

#define EL "\n"

int getCount(const char* source, int N, bool type) {
	char* grid = new char[N * N];
	memcpy(grid, source, sizeof(char) * (N * N));

	if (type)
		for (int i = 0; i < N * N; i++)
			if (grid[i] == 'R')
				grid[i] = 'G';

	int count = 0;
	int UDLR[4][2]{ {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
	while (true) {
		queue<pair<int, int>> colors;
		for (int r = 0; r < N; r++)
			for (int c = 0; c < N; c++)
				if (grid[r * N + c] != 0) {
					colors.push(make_pair(r, c));
					goto OUT;
				}
		break;
	OUT:;

		while (colors.size()) {
			auto [r, c] = colors.front();
			if (grid[r * N + c] == 0) {
				colors.pop();
				continue;
			}

			for (auto d : UDLR) {
				int dr = r + d[0];
				int dc = c + d[1];
				if (dr < 0 || dr >= N)
					continue;
				if (dc < 0 || dc >= N)
					continue;
				if (grid[dr * N + dc] == 0)
					continue;
				if (grid[dr * N + dc] == grid[r * N + c])
					colors.push(make_pair(dr, dc));
			}

			grid[r * N + c] = 0;
			colors.pop();
		}
		count++;
	}

	delete[] grid;
	return count;
}

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

	int N;
	cin >> N;

	char* grid = new char[N * N];
	for (int i = 0; i < N * N; i++)
		cin >> grid[i];

	cout << getCount(grid, N, false) << " " << getCount(grid, N, true) << EL;

	delete[] grid;
	return 0;
}

---

결과

메모리초과

---

분석

1. 큐에 너무 많은 요소가 들어감으로 인해 발생한 결과일 것이다.

2. 큐에 들어갈 정보를 더 줄이거나 다른 방법을 생각해야 한다.

3. 사실 사소한 문제가 있었다. 다녀간 칸에 몇 번 영역인지 수를 저장했는데, 이 수가 RGB 문자와 겹칠 수가 있다.

4. 다녀간 칸을 0으로 표시함으로써 이 문제를 해결했다.

---

답안

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

#define EL "\n"

int getCount(const char* source, int N, bool type) {
	char* grid = new char[N * N];
	memcpy(grid, source, sizeof(char) * (N * N));

	if (type)
		for (int i = 0; i < N * N; i++)
			if (grid[i] == 'R')
				grid[i] = 'G';

	int count = 0;
	int UDLR[4][2]{ {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
	while (true) {
		queue<pair<int, int>> colors;
		for (int r = 0; r < N; r++)
			for (int c = 0; c < N; c++)
				if (grid[r * N + c] != 0) {
					colors.push(make_pair(r, c));
					goto OUT;
				}
		break;
	OUT:;

		while (colors.size()) {
			auto [r, c] = colors.front();
			if (grid[r * N + c] == 0) {
				colors.pop();
				continue;
			}

			for (auto d : UDLR) {
				int dr = r + d[0];
				int dc = c + d[1];
				if (dr < 0 || dr >= N)
					continue;
				if (dc < 0 || dc >= N)
					continue;
				if (grid[dr * N + dc] == 0)
					continue;
				if (grid[dr * N + dc] == grid[r * N + c])
					colors.push(make_pair(dr, dc));
			}

			grid[r * N + c] = 0;
			colors.pop();
		}
		count++;
	}

	delete[] grid;
	return count;
}

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

	int N;
	cin >> N;

	char* grid = new char[N * N];
	for (int i = 0; i < N * N; i++)
		cin >> grid[i];

	cout << getCount(grid, N, false) << " " << getCount(grid, N, true) << EL;

	delete[] grid;
	return 0;
}