[백준, 10026번] 적록색약 (DFS, 깊이 우선 탐색, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 적록색약" 문제는 빨간색과 초록색의 구분이 어려운 적록 색약인 사람이 보는 지역의 구역 수와 적록색약이 아닌 사람이 보는 지역의 구역 수를 구하는 문제입니다.

 

설명이 쉽도록 적록색약인 사람은 "적록색약", 적록색약이 아닌 사람은 "정상인"이라고 칭하겠습니다.

---

 

문제의 예제 입력 1번을 예로 들어 설명하자면 위와 같이 지역이 색깔에 맞게 구분이 됩니다.

• 정상인 = 빨간색(R) = 2 + 초록색(G) = 1 + 파란색(B) = 1 ➡️ 4개의 구역
• 적록색약  = 빨간색 && 초록색(RG) = 2 + 파란색(B) = 1 ➡️ 3개의 구역

즉, 해당 문제는 적록색약과 정상인을 처리하기 위해 적록(Red & Green)을 하나의 색으로 취급하거나, 정상적인 색상 구분을 그대로 유지하여 각각의 시각에 맞게 지역을 탐색하고 구역의 수를 구하는 방식으로 접근해야 합니다.

 

저는 각각의 시각에 맞게 지역을 탐색하는 방법을 채택했습니다. 이를 해결하기 위해 두 가지 경우에 대한 탐색을 해야 합니다.

1. 정상인 기준으로 구역을 탐색
2. 적록색약 기준으로 구역을 다시 탐색

전체 코드

 

코드는 크게 main 문과 dfs함수로 구성되어 있으며, 문제의 핵심은 정상인과 적록색약 각각 시각에 맞게 지역을 탐색해야 합니다.

 

이를 활용하기위해, dfs함수를 호출할 때 is_blindness라는 플래그를 사용하여 분기처리해줬습니다.

 

1. static 변수

• N: 지역의 크기(N x N 크기)
• map: 지역의 색상을 담고 있는 2D 배열
• visited: 각 칸을 방문했는지 여부를 추적하는 2D 배열
• normal: 정상인 시각에서 구역의 수를 카운트하는 변수
• blindness: 적록색약 시각에서 구역의 수를 카운트하는 변수
• dx와 dy: 상하좌우 탐색을 위한 방향 배열

[TIL, 일일 회고] 2025.01.24 - 2차원 배열에서 8방향 이동 구현: 상하좌우 및 대각선 탐색 방법 (java)

---

2. main 문

 

• 먼저 정상인의 구역을 순회하고, 그 후 적록색약이 보는 구역을 순회합니다.
  • dfs(x, y, color, false): 정상인 시각으로 탐색.
  • dfs(x, y, color, true): 적록색약 시각으로 탐색.
• 각 구역이 발견될 때마다 정상인 구역은 normal 변수에, 적록색약 구역은 blindness 변수에 카운트됩니다.

 

3. dfs 함수

 

• x, y: 현재 탐색 중인 좌표.
• color: 현재 탐색 중인 색상.
• is_blindness: 정상인 시각(false) 또는 적록색약 시각(true)에 따라 탐색 방법이 달라집니다.
  • 적록색약 시각에서는 빨간색('R')과 초록색('G')을 동일하게 취급하여 탐색합니다.
• 탐색 중, 각 구역의 방문 여부를 체크하여 한 번도 방문하지 않은 지역을 찾고, 이를 하나의 구역으로 간주하여 카운트합니다.
• 인접한 지역을 순차적으로 탐색하면서 구역을 형성하고, 이를 반복하여 각 구역의 수를 계산합니다.

 

주의 사항❗️

 

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
[true, true, true, true, true]
[true, true, true, true, true]
[true, true, true, true, true]
[true, true, true, true, true]
[true, true, true, true, true]
4 0

 

위와 같이  적록색약과 정상인의 탐색을 완료한 후에 visited 배열을 초기화해주지 않으면, 색약 탐색과 정상인 탐색이 서로 영향을 주게 되어 결과가 틀어질 수 있습니다.

 

따라서 각각 시각에 맞게 지역을 탐색해야 하기 때문에 하나의 시각에서 지역을 탐색했으면 반드시 방문 여부를 초기화를 해줘야합니다.