[BFS]-기본-적록색약

< BFS > - < 골드 5 >

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

10026번: 적록색약

---

[ 10026 ] 적록색약

 

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

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

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

 

:: 입력 ::

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

:: 출력 ::

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

---

 

문제를 읽고 일단 BFS를 두 번 돌리는 건 피할 수 없겠다 생각했음 그래서 배열을 따로 만들어서 사용 적록색약의 경우 R과 G에 구분이 없기때문에 입력을 받을 때 1로 통일해서 받음 1트만에 성공 ><  정답코드도 BFS를 두 번 돌리는 방법을 사용하고 있음

 

  정답  코드  

#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <queue>

using namespace std;

#define Max 101

int normal[Max][Max];
int n_visit[Max][Max];
int weak[Max][Max];
int w_visit[Max][Max];

queue<pair<int, int>> Q;

int dir_x[] = { 0, -1, 0, 1 };
int dir_y[] = { 1, 0, -1, 0 };

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

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			char c;
			cin >> c;
			if (c == 'G') { normal[i][j] = 1; weak[i][j] = 1; }
			if (c == 'R') { normal[i][j] = 2; weak[i][j] = 1; }
		}
	}

	int n_cnt = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (n_visit[i][j] == 0) {
				Q.push({ i,j });
				n_visit[i][j] = 1;
				n_cnt++;
			}

			while (!Q.empty()) {
				int x = Q.front().first;
				int y = Q.front().second;
				Q.pop();

				for (int k = 0; k < 4; k++) {
					int nx = x + dir_x[k];
					int ny = y + dir_y[k];
					if (nx < 0 || nx >= n || ny < 0 || ny >= n)	continue;
					if (n_visit[nx][ny] == 1 || normal[nx][ny] != normal[x][y]) continue;

					n_visit[nx][ny] = 1;
					Q.push({ nx, ny });
				}
			}
		}
	}

	int w_cnt = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (w_visit[i][j] == 0) {
				Q.push({ i,j });
				w_visit[i][j] = 1;
				w_cnt++;
			}

			while (!Q.empty()) {
				int x = Q.front().first;
				int y = Q.front().second;
				Q.pop();

				for (int k = 0; k < 4; k++) {
					int nx = x + dir_x[k];
					int ny = y + dir_y[k];
					if (nx < 0 || nx >= n || ny < 0 || ny >= n)	continue;
					if (w_visit[nx][ny] == 1 || weak[nx][ny] != weak[x][y]) continue;

					w_visit[nx][ny] = 1;
					Q.push({ nx, ny });
				}
			}
		}
	}

	cout << n_cnt << " " << w_cnt;
}