[백준] 10026: 적록색약

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

10026번: 적록색약

아이디어

• 배열이 그렇게 크지 않아 적록색약인 경우와 아닌 경우 두 번 bfs를 해도 될 것 같음
• 방문처리 배열도 만들어서 bfs 진행해보자
• 첫 bfs함수는 색깔을 인자로 같이 넣어주어 같은 색상끼리 묶어주기
• 두 번째 bfs함수는 R,G를 같은 색상으로 인식하게 해주면 될듯 (조건문)
• 두번째 함수 돌릴 때는 방문처리 배열을 재활용하자 1이 방문이 되지 않은 것으로 인지

코드

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

# 2차원 배열로 그림 입력
paint = [list(input())[:-1] for _ in range(n)]

# 방문처리를 위한 배열 선언
check = [[0]*n for _ in range(n)]


dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

# 적록색약 미적용 dfs
def dfs(y, x, color):
    q= deque()
    q.append((y,x))
    while q:
        ey, ex = q.popleft()
        for i in range(4):
            ny = ey + dy[i]
            nx = ex + dx[i]
            if 0<=ny<n and 0<=nx<n and check[ny][nx] == 0 and paint[ny][nx] == color:
                check[ny][nx] = 1
                q.append((ny, nx))

# 적록색약 적용 dfs
def RG_dfs(y, x, color):
    q= deque()
    q.append((y,x))
    while q:
        ey, ex = q.popleft()
        for i in range(4):
            ny = ey + dy[i]
            nx = ex + dx[i]
            if color == 'B':
                if 0<=ny<n and 0<=nx<n and check[ny][nx] == 1 and paint[ny][nx] == color:
                    check[ny][nx] = 0
                    q.append((ny, nx))
            else:
                if 0<=ny<n and 0<=nx<n and check[ny][nx] == 1 and (paint[ny][nx] == 'R' or paint[ny][nx] == 'G'):
                    check[ny][nx] = 0
                    q.append((ny, nx))


# 적록색약이 아닌 경우
no_RG_cnt = 0
for i in range(n):
    for j in range(n):
        if check[i][j] == 0: # 방문 확인
            check[i][j] = 1
            color = paint[i][j]
            dfs(i,j, color)
            no_RG_cnt += 1

# 적록색약인 경우
RG_cnt = 0
for i in range(n):
    for j in range(n):
        if check[i][j] == 1:  # 방문처리 배열 재활용 
            check[i][j] = 0
            color = paint[i][j]
            RG_dfs(i,j, color)
            RG_cnt += 1


print(no_RG_cnt, RG_cnt)

맞았다

 

마무리

• 배열의 크기가 100x100 그렇게 크지 않아 위 코드가 시간초과가 나지 않았던 것 같음
• 근데 뭔가 2번의 함수를 따로 쓰지 않고 한 번에 처리하는 코드가 있을 것 같긴 해..