[문제 풀이 22] 코드 트리 - 색맹

색맹

 

• 문제 유형 : DFS
• 사용언어 : Python
• 난이도 : 실버 1
• 출처 : 코드 트리

https://www.codetree.ai/training-field/search/problems/color-blindness?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

def dfs(grid, visited, x, y, n):
    stack = [(x, y)]
    size = 0
    color = grid[x][y]

    while stack:
        cx, cy = stack.pop()
        if visited[cx][cy]:
            continue
        visited[cx][cy] = True
        size += 1

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] == color:
                stack.append((nx, ny))
    return size

# 입력 받기
n = int(input())
area = [list(input()) for _ in range(n)]
color_blind_area = [row[:] for row in area]  # 격자 복사

# 적록색약용 격자 변환
for i in range(n):
    for j in range(n):
        if color_blind_area[i][j] == 'G':
            color_blind_area[i][j] = 'R'

# 일반적인 탐색과 적록색약 탐색
visited = [[False]*n for _ in range(n)]
visited_cb = [[False]*n for _ in range(n)]

normal_zones = 0
color_blind_zones = 0

for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            dfs(area, visited, i, j, n)
            normal_zones += 1
        if not visited_cb[i][j]:
            dfs(color_blind_area, visited_cb, i, j, n)
            color_blind_zones += 1


print(normal_zones, color_blind_zones)