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)