디스크립션: 적록색약과 일반인의 시각에서 색상이 구분되는 방식이 다르게 나타나는 이 문제를 다루며, 제가 직접 구현해본 C++ 코드를 통해 두 시각에 따른 구역 수를 계산하는 방법에 대해 설명하고자 합니다. 이를 통해 알고리즘 문제 해결 과정에서 느꼈던 점도 공유할 예정입니다.
문제의 이해: 색상 구역을 나누는 기준
적록색약은 빨강과 초록의 구분이 어렵기 때문에, 같은 색으로 여겨지는 두 색상이 접했을 때 구역을 어떻게 나누는지가 중요해요. 제가 경험한 바에 따르면, 이러한 문제를 잘 이해하고 다양한 경우를 고려하는 게 핵심입니다. 먼저, 문제에서는 다음을 요구하죠.
- 크기가 N×N인 격자의 색상 표현은 R(빨강), G(초록), B(파랑) 입니다.
- 두 가지 시각에서 각 구역의 수를 세어야 합니다.
구역의 정의
구역은 다음과 같은 원칙에 따라 정의되는데요.
– 같은 색상이 인접할 경우, 같은 구역으로 간주합니다.
– 적록색약인 경우 R과 G는 같은 구역으로 취급됩니다.
| 색상 | 구역 수 (비적색약) | 구역 수 (적색약) |
|---|---|---|
| R | 1 | 1 |
| G | 1 | 1 |
| B | 1 | 1 |
| 합계 | 4 | 3 |
위의 예시에서 적록색약이 아닐 경우 4개, 적록색약의 경우 3개의 서로 다른 구역이 형성되는 걸 알 수 있습니다. 문제의 요구사항은 바로 이런 두 가지 구역의 수를 세는 것이죠.
접근 방식: DFS를 통한 그래프 탐색
제가 선택한 방법은 깊이 우선 탐색(DFS)입니다. DFS는 그래프 탐색에서 인접한 노드를 한 방향으로 계속 탐색하므로, 구역을 세기 효율적인 방법이라고 생각했어요.
DFS를 구현하는 방법
이렇게 DFS를 사용하여 구현할 수 있습니다:
- 색상 위치 기록: 입력받은 색상을 2차원 배열에 저장합니다.
- 접근 방식: 아직 방문하지 않은 노드를 발견하면 DFS를 호출하여 그 노드와 연결된 구역을 모두 방문합니다.
- 상하좌우 이동: 각 칸에서 상하좌우로 이동하며 인접한 색상이 같은지 확인 후, 진행합니다.
- 경계 체크: 인접한 노드가 격자의 경계를 넘어서는지 항상 체크해야 해요.
- 적록색약 판별: 적록색약인 경우에는 R과 G를 같다고 처리하여 DFS를 수행합니다.
구현의 코드
“`cpp
include
include
using namespace std;
int n, block_count;
char arr[101][101];
bool check[101][101];
int dx[4] = {-1, 1, 0, 0}; // 상하좌우 이동
int dy[4] = {0, 0, -1, 1};
bool dfs(int y, int x, bool color_blind) {
if (check[y][x]) return false; // 이미 방문한 경우
check[y][x] = true;
for (int k = 0; k < 4; k++) {
int next_x = x + dx[k];
int next_y = y + dy[k];
// 범위 체크
if (next_x < 0 || next_y < 0 || next_x >= n || next_y >= n || check[next_y][next_x]) continue;
if (color_blind) {
// 적록색약일 경우
if ((arr[y][x] == 'B' && arr[next_y][next_x] == 'B') ||
((arr[y][x] == 'R' || arr[y][x] == 'G') && (arr[next_y][next_x] == 'R' || arr[next_y][next_x] == 'G'))) {
dfs(next_y, next_x, true);
}
} else {
// 적록색약이 아닐 경우
if (arr[next_y][next_x] == arr[y][x]) {
dfs(next_y, next_x, false);
}
}
}
return true;
}
int main(void) {
scanf(“%d”, &n);
for (int i = 0; i < n; i++) {
scanf(“%s”, arr[i]); // 색상 행렬 입력
}
// 일반인 기준
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!check[i][j] && dfs(i, j, false)) block_count++;
}
}
printf("%d ", block_count);
memset(check, false, sizeof(check)); // 방문 기록 초기화
block_count = 0;
// 적록색약 기준
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!check[i][j] && dfs(i, j, true)) block_count++;
}
}
printf("%d", block_count);
}
“`
테스트 및 결과 확인
제가 직접 구현하고 테스트해본 결과, 입력받은 색상과 경계 조건에 따라 정확하게 결과가 나오더라구요. 이런 알고리즘 문제는 항상 다양한 입력을 받고 반응하는 구조를 만드는 게 중요하다고 생각해요.
주어진 문제에서 요구하는 두 가지 구역 수가 잘 출력되는 것을 보고 성취감을 느꼈답니다. 그 경험 속에서 많은 것을 배울 수 있었어요.
결론
이 문제를 통해 색상을 기반으로 한 그래프 탐색의 여러 요소를 이해하게 되었어요. 적록색약이라는 관점을 추가함으로써 문제의 난이도가 올라갔지만, DFS를 활용하여 두 가지 상황에 맞춘 해결책을 마련할 수 있었습니다. 앞으로도 이런 유형의 문제를 통해 더 깊은 이해를 돕고 싶어요.
키워드: 적록색약, DFS, 그래프 탐색, 알고리즘 문제, C++, 색상 구역, 문제 해결, 백준 10026, 알고리즘, 경계 조건