이 글에서는 백준 10026번 문제인 “적록색약”을 해결하기 위해 제가 알아본 바로는, DFS(Depth First Search)를 활용한 접근 방법을 소개하려고 해요. 문제의 본질은 적록색약인 사람과 아닌 사람이 보는 그림의 구역 수를 세는 것입니다. 구조적으로는 N×N 그리드로 나타낸 그림을 색상에 따라 구분해야 해요.
문제 분석과 이해
적록색약의 종류에 따라 색을 구분하는 것이 다르니, 이 두 가지 경우를 모두 생각해봐야 해요. 구역의 수를 세는데 필요한 정보는 다음과 같아요.
구역의 구분
- 색상에 따라:
- R(빨강)
- G(초록)
- B(파랑)
- 구역은 상하좌우로 인접한 색상으로 구분되지요.
| 색상 | 일반인 인식 | 적록색약 인식 |
|---|---|---|
| R | R 구역 | R 구역 |
| G | G 구역 | R 구역 |
| B | B 구역 | B 구역 |
이와 같은 데이터와 구조를 기반으로 DFS를 통해 색의 구역을 탐색해야 해요. 제가 직접 뛰어든 이 문제를 해결하기 위해서는 재귀의 깊이를 고려해야 하고, ‘재귀 깊이’를 설정하는 것이 중요해요.
DFS의 구성 요소
다음으로 DFS를 위한 기본 기능에 대해 설명드릴게요.
1. 범위 설정과 방향 탐색
탐색은 상하좌우 네 방향을 통해 진행해야 해요. Python에서의 방향 설정은 아래와 같이 배열로 구현할 수 있어요.
python
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
이렇게 설정하면, 상하좌우로 쉽게 움직일 수 있지요. 그래서, 이 방향을 기반으로 탐색할 겁니다.
2. DFS 구현하기
재귀적으로 호출하는 DFS 함수는 색상을 기준으로 특정 색상을 방문한 경우 인접한 같은 색상들을 모두 방문 처리를 해야 해요. 이를 위해 visited 리스트를 활용할 거예요. 다음과 같이 구현하였어요.
python
def dfs(x, y, color):
visited[x][y] = 1
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N and visited[nx][ny] == 0:
if graph[nx][ny] == color:
dfs(nx, ny, color)
반복을 하여 각 칸에 색상을 넣고 DFS로 탐색했어요. 기본적으로는 각 색상이 다른 경우를 구분하는 사항을 중점적으로 두었지요.
적록색약의 경우 처리하기
일반적인 탐색이 끝나고 나면, 적록색약인 경우는 초록색을 빨간색으로 바꿔줘야 해요. 그 과정을 통해 색상을 통합해보아야겠지요.
1. 색상 변경하기
이전 탐색 후, 그림을 다시 바꿔줘요. ‘G’를 ‘R’로 바꿔주는 코드:
python
for i in range(N):
for j in range(N):
if graph[i][j] == 'G':
graph[i][j] = 'R'
2. 다시 DFS 실행하기
이후에 다시 DFS를 통해 적록색약의 경우를 세어줘요.
python
visited = [[0] * N for _ in range(N)]
for color in ['R', 'B']:
# 또다시 DFS 탐색
최종 결과 출력하기
모든 탐색을 마친 후 출력 구문을 통해 결과를 보여줘야 해요.
python
print(sum, sum2)
이렇게 하여 최종적으로 적록색약 인식과 비인식의 구역 수를 구할 수 있답니다.
문제 해결의 느낀점
문제를 푸는 과정에서 파이썬의 재귀 깊이를 미리 설정해야 한다는 사실을 배웠어요. 이 작은 팁이 문제를 더 쉽게 해결하는 데 큰 도움이 되었네요.
또한, 다양한 조건들의 예외를 감안하고 실수없이 안전하게 탐색해야 하는 점에서 DFS의 중요성을 다시 한번 느꼈어요.
자주 묻는 질문 (FAQ)
적록색약 문제는 어떤 방식으로 접근하나요?
DFS를 통해 색을 탐색하고 그 구역의 개수를 세는 것이 가장 효과적이에요.
DFS의 재귀 깊이를 설정하는 방법은?
파이썬의 경우 sys.setrecursionlimit() 함수를 통해 재귀 깊이를 설정할 수 있어요.
그래프 구현은 어떻게 하나요?
2차원 리스트를 사용하여 각 칸에 R, G, B 등으로 색을 구분하여 구현합니다.
적록색약으로 보는 경우의 차이는 어떤가요?
일반인은 색을 구분하지만, 적록색약은 빨강과 초록을 구분하지 못하기 때문에 두 가지 색상이 같은 구역으로 인식됩니다.
전반적으로 제 코드와 풀이 과정을 통해서 문제의 다각적인 접근을 살펴보았고, 이를 통해 파이썬의 유용성을 느끼게 되었어요. 문제를 풀며 직접 경험한 것들이 여러분께 도움이 되면 좋겠어요.
키워드: 적록색약, DFS, 파이썬, 백준, 알고리즘, 구역 수, 탐색, 코딩테스트, 그래프, 재귀, 문제해결
이전 글: 김장배추 모종을 위한 완벽한 시기와 팁