백준 10026_적록색약 문제풀이 in C++

2022년 10월 15일 in Devlog on Algorithm

1. 문제 URL
2. 문제 요구사항
3. 접근 방법
4. 풀이 순서
5. 소스코드
6. 문제 풀이 결과

문제 URL

---

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

문제 요구사항

---

• 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
• 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다.
• 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다.
• 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

• 그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
• 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
• 둘째 줄부터 N개 줄에는 그림이 주어진다.
• 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

접근 방법

---

• 맵을 정상 맵, 색약 맵의 데이터로 구분하고, 기존 영역 구하기 방식의 BFS 탐색을 정상적인 맵 한 번, 색약 맵에서 한 번, 총 두 번 수행하면 쉽게 구할 수 있다.

풀이 순서

---

1. N과 맵의 정보를 입력 받는다. 이때, R과 G라면 색약 맵에는 N으로 통일시켜 입력 받는다.
2. 이중 for문을 이용하여 visited, visited2의 각 인덱스 값이 false 일 때, bfs 탐색한다.
   • i, j 인덱스 값과 맵의 키( R, G, B 중 어떤 것인지), 맵 정보, visited 정보를 매개변수로 준다.
   • 해당 키에 대한 영역을 탐색하며 visited / visited2를 check 해 간다.
3. 구한 정상 맵의 영역 개수와 색약 맵의 영역 개수를 출력한다.

소스코드

---

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

char normal_map[100][100];
char blindness_map[100][100];
bool visited[100][100] = { false, };
bool visited2[100][100] = { false, };
int N;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
int normal_area = 0;
int blindness_area = 0;
void input() {
	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> normal_map[i][j];

			if (normal_map[i][j] == 'R' || normal_map[i][j] == 'G') {
				blindness_map[i][j] = 'N';
			}
			else {
				blindness_map[i][j] = normal_map[i][j];
			}
		}
	}
}

void bfs(int i, int j, char key, char tmpmap[100][100], bool checkd[100][100]) {
	checkd[i][j] = true;

	queue<pair<int, int>> q;

	q.push({ i, j });

	while (!q.empty()) {
		int xx = q.front().first;
		int yy = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = xx + dx[i];
			int ny = yy + dy[i];

			if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
				if (!checkd[nx][ny] && tmpmap[nx][ny] == key) {
					q.push({ nx, ny });
					checkd[nx][ny] = true;
				}
			}
		}
	}
}

void solution() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!visited[i][j]) {
				normal_area++;
				bfs(i, j, normal_map[i][j], normal_map, visited);
			}
			if (!visited2[i][j]) {
				blindness_area++;
				bfs(i, j, blindness_map[i][j], blindness_map, visited2);
			}
		}
	}
}

void output() {
	cout << normal_area << " " << blindness_area;
}

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

	input();
	solution();
	output();

	return 0;
}

문제 풀이 결과

---