https://www.acmicpc.net/problem/10026
문제
> 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다.
> 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
> 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다.
> 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다.
> 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
> 예를 들어, 그림이 아래와 같은 경우에
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
> 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다.
(빨강 2, 파랑 1, 초록 1)
> 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다.
(빨강-초록 2, 파랑 1)
> 그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.접근
그래프 탐색이론을 사용하여 해결한다.
적록색약이 아닐 때, 색약일 때로 나눠야 하기 때문에 각각에 대해 따져줘야한다.
그래서 탐색 메소드에 색약 여부를 판단하기위한 부울값을 하나 인자로 받아주고 이 값에 따라 다음 탐색 대상을 선별할 때,
이 부울이 참이면 색약이므로 현재 색이 R,G일 땐 B를 거르고
B일땐 전부 거르도록 조건을 추가해준다.
부울이 거짓이면 일반적인 조건인 색이 다를때 거르도록 해준다.
문제해결
> 그래프 탐색 메소드에 인자로 그리드의 좌표와 색약여부를 받아준다.
> 탐색을 위해 큐를 사용하는데 다뤄야하는 변수가 좌표쌍과 그 좌표쌍이 가리키는 색(문자형)이므로 이를 구조체로 묶어 큐의 형을 정의해준다.
> 큐의 원소에 대해 탐색을 한다. 사방에 같은 색이 있는 지보기위해 사방 탐색으로 새로운 탐색 좌표를 구하는데
그리드의 범위를 벗어나면 탐색하지않고, 색약 여부에 따라 현재 색이 빨,초면 파란색만 거르고, 파면 다 거르고,
아니라면 다른색끼리 거르도록 조건을 잡아준다.
> 이 조건을 모두 만족하고 나오면 큐에 만족하는 다음 탐색 대상의 좌표와, 그 좌표가 가리키는 색을 넣어 계속 해준다.
>main함수에서 그리드를 입력받고 t를 색약 여부인 0,1로 잡고 이를 부울값으로 사용한다.
각 t마다 방문처리를 초기화 해야 제대로 결과를 얻는다.
> 좌표를 돌며 이미 봤던 곳은 건너뛰며 색의 구역을 탐색한다. 탐색 메소드가 끝나면 구역이 나왔다는 것이므로 cnt값을 각각 색약, 색약아닐 때로 나누어 누적한다.
> 이를 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int N;
int dir[4] = { -1, 1, 0, 0 };
int dic[4] = { 0, 0, -1, 1 };
vector<vector<char>> grid;
vector<vector<bool>> visited;
struct dot {
pair<int, int> rc;
char color;
};
void Grid(pair<int, int> start, bool cweak)
{
queue<dot> q;
char startcolor = grid[start.first][start.second];
q.push({ start, startcolor });
while (!q.empty())
{
int fr = q.front().rc.first;
int fc = q.front().rc.second;
char fcolor = q.front().color;
q.pop();
if (visited[fr][fc]) continue;
visited[fr][fc] = true;
for (int i = 0; i < 4; i++)
{
int nr = fr + dir[i];
int nc = fc + dic[i];
if (nr < 0 || nr >= N) continue;
if (nc < 0 || nc >= N) continue;
char ncolor = grid[nr][nc];
if (cweak)
{
if (fcolor == 'R' || fcolor == 'G')
{
if (ncolor == 'B') continue;
}
if (fcolor == 'B')
{
if (ncolor != 'B') continue;
}
}
else
if (fcolor != ncolor) continue;
if (!visited[nr][nc]) q.push({ {nr, nc}, ncolor });
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
grid.assign(N, vector<char>(N));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++) cin >> grid[i][j];
}
int cnt[2] = { 0, 0 };
for (int t = 0; t < 2; t++) //색약 여부 bool
{
visited.assign(N, vector<bool>(N, false));
for (int i = 0; i < N; i++) //행
{
for (int j = 0; j < N; j++) //열
{
if (visited[i][j]) continue;
Grid({ i,j }, t);
cnt[t]++;
}
}
}
cout << cnt[0] << " " << cnt[1] << '\n';
}
후기
기존의 그래프 탐색을 이용하여 쉽게 구상은 했지만
색약, 색약 아님에 대해 두개의 탐색 메소드를 만들면 비효율적일거 같아서 이를 한 메소드에서 다 처리하느라 좀 헷갈렸다.
색약일때, 아닐 때에 대해 조건문으로 검증하는 부분이 좀 지저분해서 제출 하고 난 뒤 이를 깔끔하게 하는 법을 알아보았다.
char norm(char c, bool cweak)
{
if (!cweak) return c;
if (c == 'R' || c == 'G') return 'X';
return 'B';
}
새로 함수를 하나 만들어서 입력받은 cweak에 따라
cweak이 참이면 R과 G를 x라는 하나의 색으로 통합시켜 따지고, 거짓이면 그대로 return해 원래 자신의 색을 가지도록한다.
이 메소드를 통해 탐색에서 좌표를 가져올 때마다
fcolor = norm(fcolor, cweak)
ncolor = norm(ncolor, cweak)으로 변환해주고
조건문에선 이미 다 처리를 했기 때문에
if (fcolor != ncolor) continue; 로 딸깍 하면 되는거였다.
