콘텐츠로 건너뛰기

적록색약 문제 해결하기: DFS를 통한 영역 개수 세기



적록색약 문제 해결하기: DFS를 통한 영역 개수 세기

제가 직접 경험해본 바로는, 백준의 10026번 적록색약 문제는 DFS(깊이 우선 탐색) 알고리즘을 통해 효율적으로 해결할 수 있었습니다. 이 문제에서는 적록색약인 경우와 아닌 경우를 구분하여 구역의 개수를 세는 것이 핵심입니다. 이 글에서는 문제를 해결하기 위한 접근 방식을 설명하고, 코드 구현 방법을 자세히 안내드리겠습니다.

 

👉👉적록색약 문제 해결하기: 바로 확인

 

목차

문제 개요 및 나의 접근 방법

문제는 NxN 그리드에 R(빨간색), G(초록색), B(파란색) 중 하나의 색으로 채워진 셀들이 있습니다. 색맹이 있는 경우 R과 G는 동일한 색으로 간주됩니다. 주어진 그리드에서 구역의 개수를 세어야 합니다.



  1. 구역 개수 개념 이해하기

    • 비색맹에서는 빨강, 초록, 파랑으로 각각 구역을 나누고, 색맹에서는 빨강과 초록을 하나의 구역으로 합쳐서 계산합니다.

  2. DFS 알고리즘 사용

    • 구역을 찾기 위해 인접한 같은 색상을 탐색할 때 DFS를 사용했습니다. 이로 인해 연결된 구역을 쉽게 탐색할 수 있었습니다.

DFS 구현 단계

1. 전처리: 데이터 입력

먼저, 문제의 조건을 충족시키기 위해 입력받는 데이터나 변수를 설정합니다. 크기가 최대 100인 NxN 그리드를 저장할 배열을 선언합니다.

cpp
char arr[101][101]; // NxN 색 배열
bool check[101][101]; // 방문 여부 체크
check 배열은 각 셀의 방문 여부를 기록하기 위해 사용되며, 인접한 셀을 탐색할 때 유용합니다.

2. DFS 정의 및 탐색 로직

“`cpp
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;

}
“`
여기서는 색상을 구분하여 다음 위치를 탐색하는 로직을 구현하였습니다.

3. 반복문을 통한 구역 탐색

주어진 그리드의 모든 셀에 대해 DFS를 수행하여 구역의 개수를 줄여나갑니다. 탐색이 끝난 후에는 check 배열을 초기화하여 색맹 여부에 따라 다시 계산합니다.

cpp
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
if (!check[i][j] && dfs(i, j, false)) block_count++;
}
}

구현 및 결과 출력

모든 과정을 마치고 나면 결과를 출력하는 단계가 남습니다. 두 가지 구역 개수를 별도로 출력해주면 됩니다.

cpp
printf("%d ", block_count); // 비색약 구역 수
memset(check, 0, sizeof(check)); // 검사 배열 초기화

이러한 방식으로 적록색약 문제를 해결했습니다. 코드 구현 후 문제 테스트를 통해 생각했던 만큼의 정확한 결과를 도출해낼 수 있었습니다.

마무리하며

이번 문제를 통해 DFS 알고리즘의 활용과 색상 구별 문제를 효과적으로 해결하는 방법을 배우게 되었습니다. 이를 통해 구역의 개수를 세는 문제에 대한 대처 능력을 향상시킬 수 있었습니다. 다양한 문제를 풀어보며 경험을 쌓는 것이 중요하다는 것을 다시 한번 느꼈습니다.

FAQ

DFS가 무엇인가요?

DFS는 깊이 우선 탐색(Depth First Search)의 약자로, 그래프의 노드를 탐색하기 위해 재귀 또는 스택을 활용하는 알고리즘입니다.

색약은 어떤 영향을 미치나요?

적록색약은 빨간색과 초록색의 구별이 힘들어 동일한 색으로 인식하는 경향이 있어, 문제에서 색 구역의 개수를 다르게 계산하게 됩니다.

이 알고리즘은 어떤 응용이 있나요?

그래프 탐색 알고리즘은 경로 찾기, 연결 요소 분리 및 패턴 탐지와 같이 많은 분야에 응용될 수 있습니다.

이 문제를 통해 무엇을 배웠나요?

DFS의 기본 개념과 색 구별 문제를 해결하는 여러 방법을 통해 효율적인 문제 해결 능력을 향상시킬 수 있었습니다.

키워드: 백준, 적록색약, DFS, 알고리즘, 색깔 구역, 문제 해결, C++, 그래프 탐색, 경계 체크, 재귀 호출, 색상 구별

이전 글: 김장배추 모종을 위한 완벽한 시기와 팁

함께보면 좋은글!