코딩 테스트 2번 문제였고 풀지 못하였다.
NxN 그래프가 주어졌을 때, 구역의 개수를 세는 문제이다.
단, 적록 색약이 아닌 사람이 그래프를 봤을 때와, 적록 색약인 사람이 그래프를 봤을 때 각각 구역의 개수가 몇개로 보이는 지 다르기 때문에 이를 차례로 출력하면 된다.
적록 색약은 빨간색과 초록색의 차이를 거의 느끼지 못하는 것을 말한다. (R이 G으로 보임)
<적록 색약이 아닌 사람이 봤을 때> 구역 개수: 4개
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
<적록 색약인 사람이 봤을 때> 구역 개수: 3개
GGGBB
GGBBB
BBBGG
BBGGG
GGGGG
from collections import deque
n = int(input())
# 원래 그래프
graph = [input() for _ in range(n)]
# 적록 색약인 사람에게 보이는 그래프
new_graph = [line.replace('R', 'G') for line in graph]
def count_section(graph):
count = 0
# 상하좌우로 탐색할 좌표 차
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 방문 여부 표시
visited = set()
# 그래프 탐색
for x in range(n):
for y in range(n):
if (x, y) not in visited:
count += 1
queue = deque([(x, y)])
visited.add((x, y))
color = graph[x][y] # 현재 색깔을 기준으로 탐색
# 그 색깔과 같은 애들을 탐색한다. (큐가 비워질 때까지가 한 사이클.)
while queue:
popped_x, popped_y = queue.pop()
# 4방향으로 탐색
for i in range(4):
nx = popped_x + dx[i]
ny = popped_y + dy[i]
if 0 <= nx < n and 0 <= ny < n:
if (nx, ny) not in visited and graph[nx][ny] == color:
queue.appendleft((nx, ny))
visited.add((nx, ny))
return count
print(count_section(graph), count_section(new_graph))
