알고리즘 문제
[백준] 10026번 적록색약
feelcoding
2020. 2. 6. 01:58
728x90
10026번: 적록색약
문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은
www.acmicpc.net
BFS로 풀었다.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n;
int main() {
cin >> n;
vector<vector<char>> v(n);
vector<vector<bool>> visited(n);
for (int i = 0; i < n; i++) {
v[i] = vector<char>(n);
visited[i] = vector<bool>(n);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> v[i][j];
}
}
int normalCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j]) {
normalCount++;
if (v[i][j] == 'R') {
queue<pair<int, int>> q;
q.push(make_pair(i, j));
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
if (!visited[cur.first][cur.second]) {
visited[cur.first][cur.second] = true;
if (cur.first + 1 < n && !visited[cur.first + 1][cur.second] && v[cur.first + 1][cur.second] == 'R') {
q.push(make_pair(cur.first + 1, cur.second));
}
if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second] && v[cur.first - 1][cur.second] == 'R') {
q.push(make_pair(cur.first - 1, cur.second));
}
if (cur.second + 1 < n && !visited[cur.first][cur.second + 1] && v[cur.first][cur.second + 1] == 'R') {
q.push(make_pair(cur.first, cur.second + 1));
}
if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1] && v[cur.first][cur.second - 1] == 'R') {
q.push(make_pair(cur.first, cur.second - 1));
}
}
}
}
else if (v[i][j] == 'G') {
queue<pair<int, int>> q;
q.push(make_pair(i, j));
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
if (!visited[cur.first][cur.second]) {
visited[cur.first][cur.second] = true;
if (cur.first + 1 < n && !visited[cur.first + 1][cur.second] && v[cur.first + 1][cur.second] == 'G') {
q.push(make_pair(cur.first + 1, cur.second));
}
if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second] && v[cur.first - 1][cur.second] == 'G') {
q.push(make_pair(cur.first - 1, cur.second));
}
if (cur.second + 1 < n && !visited[cur.first][cur.second + 1] && v[cur.first][cur.second + 1] == 'G') {
q.push(make_pair(cur.first, cur.second + 1));
}
if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1] && v[cur.first][cur.second - 1] == 'G') {
q.push(make_pair(cur.first, cur.second - 1));
}
}
}
}
else if (v[i][j] == 'B') {
queue<pair<int, int>> q;
q.push(make_pair(i, j));
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
if (!visited[cur.first][cur.second]) {
visited[cur.first][cur.second] = true;
if (cur.first + 1 < n && !visited[cur.first + 1][cur.second] && v[cur.first + 1][cur.second] == 'B') {
q.push(make_pair(cur.first + 1, cur.second));
}
if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second] && v[cur.first - 1][cur.second] == 'B') {
q.push(make_pair(cur.first - 1, cur.second));
}
if (cur.second + 1 < n && !visited[cur.first][cur.second + 1] && v[cur.first][cur.second + 1] == 'B') {
q.push(make_pair(cur.first, cur.second + 1));
}
if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1] && v[cur.first][cur.second - 1] == 'B') {
q.push(make_pair(cur.first, cur.second - 1));
}
}
}
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
visited[i][j] = false;
if (v[i][j] == 'G')
v[i][j] = 'R';
}
}
int abnormalCount = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j]) {
abnormalCount++;
if (v[i][j] == 'R') {
queue<pair<int, int>> q;
q.push(make_pair(i, j));
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
if (!visited[cur.first][cur.second]) {
visited[cur.first][cur.second] = true;
if (cur.first + 1 < n && !visited[cur.first + 1][cur.second] && v[cur.first + 1][cur.second] == 'R') {
q.push(make_pair(cur.first + 1, cur.second));
}
if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second] && v[cur.first - 1][cur.second] == 'R') {
q.push(make_pair(cur.first - 1, cur.second));
}
if (cur.second + 1 < n && !visited[cur.first][cur.second + 1] && v[cur.first][cur.second + 1] == 'R') {
q.push(make_pair(cur.first, cur.second + 1));
}
if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1] && v[cur.first][cur.second - 1] == 'R') {
q.push(make_pair(cur.first, cur.second - 1));
}
}
}
}
else if (v[i][j] == 'B') {
queue<pair<int, int>> q;
q.push(make_pair(i, j));
while (!q.empty()) {
pair<int, int> cur = q.front();
q.pop();
if (!visited[cur.first][cur.second]) {
visited[cur.first][cur.second] = true;
if (cur.first + 1 < n && !visited[cur.first + 1][cur.second] && v[cur.first + 1][cur.second] == 'B') {
q.push(make_pair(cur.first + 1, cur.second));
}
if (cur.first - 1 >= 0 && !visited[cur.first - 1][cur.second] && v[cur.first - 1][cur.second] == 'B') {
q.push(make_pair(cur.first - 1, cur.second));
}
if (cur.second + 1 < n && !visited[cur.first][cur.second + 1] && v[cur.first][cur.second + 1] == 'B') {
q.push(make_pair(cur.first, cur.second + 1));
}
if (cur.second - 1 >= 0 && !visited[cur.first][cur.second - 1] && v[cur.first][cur.second - 1] == 'B') {
q.push(make_pair(cur.first, cur.second - 1));
}
}
}
}
}
}
}
cout << normalCount << endl;
cout << abnormalCount << endl;
return 0;
}728x90