적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
예를 들어, 그림이 아래와 같은 경우에
적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
입력
- 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
- 둘째 줄부터 N개 줄에는 그림이 주어진다.
- 예제입력
출력
- 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
🔎 문제 파악
📌 바둑판식 평면상에서 구역의 수를 계산해야 하므로 BFS를 이용한다.
📌 정상인과 적록색약인 사람의 경우를 다른 함수로 작성한다. 하지만 기본적인 골격은 같다. 단지 조건문을 몇개 달아서 적록색약인 상황에 대비할 것이다.
🔑 BFS
연결되어 있는 칸이 몇 개의 영역을 가지는지 계산할 때는 그래프 알고리즘 중 하나인 BFS를 사용할 것이다. DFS로 구현이 가능하긴 recursive call을 사용하여 최악의 경우 100 X 100칸을 모두 읽어들인다면 시간 초과에 걸릴 가능성이 높다 (아마 무조건 시간초과가 걸릴 것이다) .
BFS의 기본구조는 무조건 암기하고 있도록 하자.
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> adj; // Adjacency list
vector<bool> visit; // vector for checking visited node
/**
* visit는 초기화 되어있는 상태라고 가정한다.
* Param - start; 시작 노드를 입력
* return - vector<int>; 탐색 순서 벡터를 반환
*/
vector<int> bfs(int start) {
vector<int> order; // 탐색 순서를 넣을 벡터 선언
queue<int> q;
q.push(start);
visit[start] = true;
while(!q.empty()) {
int now = q.front();
q.pop();
order.push_back(now);
for(int i = 0;i < adj[now].size();i++){
int next = adj[nonw][i];
if(!visit[next]) {
q.push(next);
visit[next] = true;
}
}
}
return order;
}⭐️ 물론, 기본 코드를 바로 사용하지 못한다. 기본코드는 Adjacency list 형태로 구현된 그래프 구조에서 사용할 수 있도록 만들어져 있으므로 문제에서 정한 바둑판식 구조에서 사용할 수 있도록 적절히 바꿔주자.
📚 자료구조
바둑판식 구조이므로 RGB를 입력받을 char type "map" 2차원 배열과 방문여부를 저장할 bool type "visit" 2차원 배열을 선언한다.
BFS에서 사용할 queue는 x좌표와 y좌표를 함께 넣을 수 잇게 pair<int, int>를 원소로 가진다. 또한 바둑판위에서 한칸씩 움직일 때 발생하는 좌표 변화율을 상수로 저장할 크기가 4인 int형 배열 dx, dy 두개를 선언한다.
char map[101][101];
bool visit[101][101];
queue<pair<int, int>> q;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };🚀 최종 코드
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
using namespace std;
char map[101][101];
bool visit[101][101];
queue<pair<int, int>> q;
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
void init(int N) {
for (int i = 1;i <= N;i++)
for (int j = 1;j <= N;j++)
visit[i][j] = false;
}
int bfs_normal(int N) {
int x, y, region = 0;
char pivot;
for (int i = 1;i <= N;i++) {
for (int j = 1;j <= N;j++) {
if (!visit[i][j]) {
region++;
pivot = map[i][j];
x = j; y = i;
q.push(make_pair(y, x));
visit[y][x] = true;
while (!q.empty()) {
y = q.front().first;
x = q.front().second;
q.pop();
for (int h = 0;h < 4;h++) {
int next_y = y + dy[h];
int next_x = x + dx[h];
if (map[next_y][next_x] == pivot && !visit[next_y][next_x]) {
q.push(make_pair(next_y, next_x));
visit[next_y][next_x] = true;
}
}
}
}
}
}
return region;
}
int bfs_colorweakness(int N) {
int x, y, region = 0;
char pivot;
for (int i = 1;i <= N;i++) {
for (int j = 1;j <= N;j++) {
if (!visit[i][j]) {
region++;
pivot = map[i][j];
x = j; y = i;
q.push(make_pair(y, x));
visit[y][x] = true;
while (!q.empty()) {
y = q.front().first;
x = q.front().second;
q.pop();
for (int h = 0;h < 4;h++) {
int next_y = y + dy[h];
int next_x = x + dx[h];
if (pivot == 'B') {
if (map[next_y][next_x] == pivot && !visit[next_y][next_x]) {
q.push(make_pair(next_y, next_x));
visit[next_y][next_x] = true;
}
}
else {
if ((map[next_y][next_x] == 'R' || map[next_y][next_x] == 'G') && !visit[next_y][next_x]) {
q.push(make_pair(next_y, next_x));
visit[next_y][next_x] = true;
}
}
}
}
}
}
}
return region;
}
int main() {
int N;
scanf("%d", &N);
for (int i = 1;i <= N;i++) {
for (int j = 0;j <= N;j++) {
scanf("%c", &map[i][j]);
}
}
int result1 = bfs_normal(N);
init(N);
int result2 = bfs_colorweakness(N);
printf("%d %d", result1, result2);
}⌛️ 문제 해설
void init(int N) {
for (int i = 1;i <= N;i++)
for (int j = 1;j <= N;j++)
visit[i][j] = false;
}두번의 BFS를 계산하는 동안 같은 visit 배열을 사용하기 위해 초기화 함수를 작성해주었다.
int bfs_normal(int N) {
int x, y, region = 0;
char pivot;
for (int i = 1;i <= N;i++) {
for (int j = 1;j <= N;j++) {
if (!visit[i][j]) {
region++;
pivot = map[i][j];
x = j; y = i;
q.push(make_pair(y, x));
visit[y][x] = true;
while (!q.empty()) {
y = q.front().first;
x = q.front().second;
q.pop();
for (int h = 0;h < 4;h++) {
int next_y = y + dy[h];
int next_x = x + dx[h];
if (map[next_y][next_x] == pivot && !visit[next_y][next_x]) {
q.push(make_pair(next_y, next_x));
visit[next_y][next_x] = true;
}
}
}
}
}
}
return region;
}정상인 코드의 경우 BFS를 시작하게되는 map[i][j]를 pivot 으로 삼고 BFS의 다음 계산의 조건을 if (map[next_y][next_x] == pivot && !visit[next_y][next_x]) 즉, 주변위치의 알파벳이 pivot과 같고 아직 방문하지 않은 상태면 큐에 해당 좌표를 푸시한다.
int bfs_colorweakness(int N) {
int x, y, region = 0;
char pivot;
for (int i = 1;i <= N;i++) {
for (int j = 1;j <= N;j++) {
if (!visit[i][j]) {
region++;
pivot = map[i][j];
x = j; y = i;
q.push(make_pair(y, x));
visit[y][x] = true;
while (!q.empty()) {
y = q.front().first;
x = q.front().second;
q.pop();
for (int h = 0;h < 4;h++) {
int next_y = y + dy[h];
int next_x = x + dx[h];
if (pivot == 'B') {
if (map[next_y][next_x] == pivot && !visit[next_y][next_x]) {
q.push(make_pair(next_y, next_x));
visit[next_y][next_x] = true;
}
}
else {
if ((map[next_y][next_x] == 'R' || map[next_y][next_x] == 'G') && !visit[next_y][next_x]) {
q.push(make_pair(next_y, next_x));
visit[next_y][next_x] = true;
}
}
}
}
}
}
}
return region;
}색약인의 경우 정상인 코드와 거의 유사하지만 pivot이 'B'인 경우오 그렇지 않은 경우를 나눠서 생각해주어야한다. pivotr이 'B'가 아니라면 다음번 알파벳이 'R' 또는 'G' 이고 아직 방문하지 않은 조건을 충족했을 때, 큐에 다음번 좌표를 푸시한다.
