제가 직접 경험해본 결과로는, 적록색약 문제는 BFS를 활용하여 구역의 개수를 세는 것이 핵심이에요. 이 문제를 해결하기 위해 주어진 조건을 잘 파악하고, BFS 알고리즘을 적절히 활용하는 것이 중요하지요. 이제 아래를 읽어보시면 이 문제의 해결 과정을 단계별로 소개할게요.
문제 이해하기 및 그림 그리기
적록색약 문제는 주어진 N×N 그리드에서 색깔 정보를 가지고 구역을 파악하는 것이에요. 여기서 구역은 같은 색깔로 인접한 칸의 집합을 의미하게 되고요. 색깔의 형태는 R(빨강), G(초록), B(파랑)로 구분되지요. 제가 알아본 바로는, 빨간색과 초록색 구역은 적록색약인 사람에게는 같은 색깔로 인식될 수 있어요. 따라서 두 가지 케이스에 대해 BFS를 통해 구역의 개수를 체크하게 되었어요.
- 케이스 1: R-G가 같은 그룹으로 묶이고, B는 별개로 처리.
- 케이스 2: R, G, B를 각각 별개의 그룹으로 묶어 처리.
이렇게 두 가지 케이스의 구역 개수를 재야 하므로, BFS를 두 번 사용하는 것이 효과적이에요. 이 과정에서 사용하게 될 4방향 이동을 위한 배열도 필요하답니다.
BFS 구현하기
BFS를 구현하기 위한 코드를 작성했어요. 다음 코드는 제 접근 방식을 보여준답니다.
“`python
import sys
from collections import deque
n = int(sys.stdin.readline())
m = []
dy, dx = [1, -1, 0, 0], [0, 0, 1, -1]
for _ in range(n):
m.append([i for i in sys.stdin.readline().strip()])
ans = [0, 0]
“`
소스코드에서는 첫 번째로 입력된 N을 읽고, N×N 크기의 배열 m을 초기화했어요. 그 다음, 4방향으로 이동하기 위한 dy, dx 배열을 설정하였지요. 이러한 배열은 BFS 탐색 중 이동 방향을 조절하는 데 필수적이에요.
첫 번째 BFS (R-G, B 구분)
이제 BFS를 통해 첫 번째 케이스를 처리해볼 거예요. 빨간색과 초록색을 같은 그룹으로 묶고, 파란색은 따로 처리하는 코드는 다음과 같답니다.
“`python
v = [[-1] * n for _ in range(n)]
ret = 0
for i in range(n):
for j in range(n):
q = deque()
if m[i][j] == “R” or m[i][j] == “G”:
if v[i][j] == -1:
v[i][j] = ret
q.append((i, j))
while q:
cy, cx = q.popleft()
for k in range(4):
ty, tx = cy + dy[k], cx + dx[k]
if 0 <= ty < n and 0 <= tx < n:
if v[ty][tx] == -1 and (m[ty][tx] == “R” or m[ty][tx] == “G”):
v[ty][tx] = ret
q.append([ty, tx])
“`
위 코드에서는 BFS를 통해 R 및 G 색상을 격리된 그룹으로 묶고, 그 그룹의 크기를 증가 시키는 과정을 보여주어요.
두 번째 BFS (R, G, B 구분)
첫 번째 BFS가 끝났다면, 두 번째 BFS를 수행해 R, G, B 각각 따로 구분해볼 차례랍니다.
“`python
v = [[-1] * n for _ in range(n)]
ret = 0
for i in range(n):
for j in range(n):
q = deque()
if v[i][j] == -1:
v[i][j] = ret
q.append((i, j))
while q:
cy, cx = q.popleft()
for k in range(4):
ty, tx = cy + dy[k], cx + dx[k]
if 0 <= ty < n and 0 <= tx < n:
if v[ty][tx] == -1 and m[ty][tx] == m[cy][cx]:
v[ty][tx] = ret
q.append([ty, tx])
“`
이 코드는 R, G, B 각각의 색깔로 구역을 나누어 BFS를 진행하는 방식이에요. 이 과정을 통해 결국 두 가지 구역 개수를 찾아내게 되는 것이지요.
결과 출력하기
각각의 BFS에서 구한 결과는 ans라는 배열에 저장되어요. 이렇게 두 구역 개수를 출력하는 과정은 다음과 같이 진행해요.
“`python
ans[0] = ret # 첫 번째 BFS 결과
ret = 0 # 초기화
두 번째 BFS를 동일하게 반복
ans[1] = ret # 두 번째 BFS 결과
print(” “.join(str(i) for i in reversed(ans)).strip())
“`
이렇게 구한 구역 개수는 적록색약인 사람의 시각과 일반적인 사람의 시각에서 각각 확인할 수 있게끔 출력되죠.
마무리
이 문제는 BFS의 기본 개념을 활용하여 색깔을 구분하고 구역을 세는 것이 핵심이에요. 저 또한 이 코드를 통해 BFS의 이해가 깊어졌어요. 문제를 해결함으로써 BFS의 활용도를 더욱 높일 수 있었답니다.
자주 묻는 질문 (FAQ)
BFS와 DFS의 차이는 무엇인가요?
BFS는 너비 우선 탐색으로, 한 레벨의 모든 노드를 탐색한 후 다음 레벨로 이동하는 방식을 취합니다. 반면 DFS는 깊이 우선 탐색으로, 가능한 한 깊은 노드까지 먼저 탐색해 나가요.
적록색약 문제에서 BFS가 쉬운가요?
그림 같은 형태에서 구역을 세는 데 사용되므로 조금 복잡해 보일 수 있지만, 두 번의 BFS로 나누어 처리하면 효율적으로 해결할 수 있어요.
문제 해결 과정에서 어려운 부분은 어떤 것이었나요?
초기 코딩을 하면서 R과 G를 같은 그룹으로 묶어주는 부분이 혼동스러울 수 있었어요. 다만, 조건을 명확히 하고 반복문을 체계적으로 구성하니 해결할 수 있었지요.
결과를 출력할 때의 주의점은 무엇인가요?
각각의 BFS가 끝난 뒤, 그 결과를 배열에 잘 저장하고 이를 리스트로 출력하는 과정이 중요하답니다. 올바른 방식으로 결과를 출력해 사용자에게 올바른 정보를 주는 것이 핵심이에요.
적록색약 문제를 통해 BFS를 깊게 이해하는 유익한 경험이었어요. 여러분도 다양한 알고리즘 문제를 풀며 실력을 쌓아보세요!
키워드: 적록색약, BFS, Python, 구역개수, 알고리즘, 문제해결, 코딩, 프로그래밍, 탐색, 백준, 파이썬