Algorithm/BOJ

[백준] 10026 적록색약 (파이썬 python)

YOONJELLY 2024. 3. 14. 23:00

 

 

문제 링크

 

https://www.acmicpc.net/problem/10026

 

10026번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

 

 

문제 풀이

 

적록색약인 사람과 아닌 사람을 flag로 구분하여

bfs 탐색 내에서 'R', 'G'를 구분할지 말지만 구현해주면 되는 쉬운 BFS 문제였습니다.

 

from collections import deque

def bfs(i, j, flag, visited):
    q = deque()
    q.append([i, j])
    visited[i][j] = 1
    color = graph[i][j]
    while q:
        x, y = q.popleft()
        for dir in range(4):
            nx, ny = x + dx[dir], y + dy[dir]
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                if (color == 'R' or color == 'G') and flag:
                    if graph[nx][ny] == 'R' or graph[nx][ny] == 'G':
                        q.append([nx, ny])
                        visited[nx][ny] = 1
                else:
                    if graph[nx][ny] == color:
                        q.append([nx, ny])
                        visited[nx][ny] = 1
    return 1


n = int(input())
graph = [list(input().strip()) for _ in range(n)]
visited = [[0] * n for _ in range(n)]
rg_visited = [[0] * n for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
result = 0
rg_result = 0
# 적록색약이 아닌 사람
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            result += bfs(i, j, False, visited)
# 적록색약인 사람
for i in range(n):
    for j in range(n):
        if not rg_visited[i][j]:
            rg_result += bfs(i, j, True, rg_visited)
print(result, rg_result)