알고리즘/백준 문제풀이

[boj] 백준 10026 적록색약 python 풀이

감자156 2023. 4. 19. 22:48
반응형

적록 색약일 때와 아닐 때의 MAP을 따로 생성하여 각각  bfs 돌려줌. 적록 색약일 경우에 R, G를 다 R로 저장해서 풀이함. 

 

문제

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

 

10026번: 적록색약

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

www.acmicpc.net

 

풀이

import sys
input = sys.stdin.readline
from collections import deque

N = int(input().strip())
MAP = [list(str(input())) for _ in range(N)]
MAP_RG = []

for i in range(N):
    tmp = []
    for j in range(N):
        if MAP[i][j] == 'G': 
            tmp.append('R') # 적록 색약은 한 색으로 보임
        else:
            tmp.append(MAP[i][j])        
    MAP_RG.append(tmp)

move = [(-1,0), (0,1), (1,0), (0,-1)]

def bfs(q, MAP, i, j):
    q.append((i, j)) 
    color = MAP[i][j]
    MAP[i][j] = 0

    while q:
        x,y = q.popleft()

        for tx, ty in move:
            nx = x + tx
            ny = y + ty
            
            if 0<=nx<N and 0<=ny<N and MAP[nx][ny] == color:
                MAP[nx][ny] = 0
                q.append((nx,ny))
                    

q = deque()
not_q = deque()
cnt, rg_cnt = 0, 0
    
for i in range(N):
    for j in range(N):
        if MAP[i][j] != 0:
            bfs(q, MAP, i, j) # 적록색약
            cnt += 1
        if MAP_RG[i][j] != 0:
            bfs(not_q, MAP_RG, i, j) # 색약 X
            rg_cnt += 1

print(cnt, rg_cnt)
반응형