[백준 C++] 10026 적록색약
문제
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
예를 들어, 그림이 아래와 같은 경우에
적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.
출력
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
https://www.acmicpc.net/problem/10026
풀이
색칠하는 개념을 떠올려보았다,
R -> G -> B순으로한다면
R에해당하는 아무 좌표하나를 찾아서 BFS로 같은 R만 모두 칠한다.
그리고 남은 R이있다면 반복하여
반복한 횟수를 체크.
G, B도 마찬가지고,
적록색약도 구해야하므로 R 과 G를 같은색으로 보고도 반복해본다.
- 프로그램의 메인부분
- 색을 칠하는 부분
- 색을 칠하기전에, 색의 위치를 찾는 부분
위치를 pair<int, int>로 리턴한다.
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using std::pair; using std::queue;
typedef pair<int, int> pii;
int n, R=0, G=0, B=0, RG=0;
char** picture, **check;
bool** visited;
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };
queue<pii> loc;
void func();
void init();
void clear();
bool checkColor(char c1, char c2, char**& check);
pii findColor(char c1, char c2, char**& check);
void pastePicture();
void func() {
pastePicture();
while (checkColor('R', 'R', check)) R++;
while (checkColor('G', 'G', check)) G++;
while (checkColor('B', 'B', check)) B++;
pastePicture();
while (checkColor('R', 'G', check)) RG++;
printf("%d %d", R + G + B, RG + B);
}
void clear() {
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) visited[i][j] = false;
}
void pastePicture() {
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) check[i][j] = picture[i][j];
}
//해당 색상을 하나 찾아서 BFS를 진행하여 같은 색상만 지워간다.
//만약 해당 색상이 남아있지않으면 false 리턴
bool checkColor(char c1, char c2, char**&check) {
clear();
pii p = findColor(c1, c2, check);
int start_x = p.first;
int start_y = p.second;
if (start_x == -1 && start_y == -1) return false;
loc.push({ start_x, start_y });
check[start_x][start_y] = 'X';
visited[start_x][start_y] = true;
while (!loc.empty()) {
int x = loc.front().first;
int y = loc.front().second;
loc.pop();
for (int dir = 0; dir < 4; dir++) {
int xx = x + dx[dir];
int yy = y + dy[dir];
if (xx < 0 || yy < 0 || xx == n || yy == n) continue; //올바르지않은범위이면 제외
if (check[xx][yy] != c1 && check[xx][yy] != c2) continue; //다른색이면 제외
if (!visited[xx][yy]) {
visited[xx][yy] = true;
check[xx][yy] = 'X'; //찾았음을 체크
loc.push({ xx, yy });
}
}
}
return true;
}
pii findColor(char c1, char c2, char**&check) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (check[i][j] == c1 || check[i][j] == c2)
return { i, j };
return { -1, -1 };
}
void init() {
scanf("%d", &n);
picture = new char* [n];
visited = new bool* [n];
check = new char* [n];
for (int i = 0; i < n; i++) {
picture[i] = new char[n];
visited[i] = new bool[n] ;
check[i] = new char[n];
char _;
scanf("%c", &_);
for (int j = 0; j < n; j++) {
scanf("%c", &picture[i][j]);
}
}
}
int main() {
init();
func();
return 0;
}
Author And Source
이 문제에 관하여([백준 C++] 10026 적록색약), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cldhfleks2/10026저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)