[백준] 10026. 적록색약 (Python)

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

10026번: 적록색약

 

✏️ BFS

• 적록색약인 사람이 보았을 때와 적록색약이 아닌 사람이 보았을 때의 구역 수를 구하는 문제
• 적록색약일 때와 아닐 때를 구분하여 2개의 visit 배열과 count, BFS 함수를 만들어 주었다.
• 이중for문으로 visit에 체크가 되지 않았을 때 BFS를 돌리는데, rgBfs(적록색약 BFS)는 색이 R이거나 G일 때만 돌려주었다.
• 만약 현재 색상이 "B"라면 적록색약 유무가 영향을 주지 않으므로, 일반 bfs에서 count와 rgCount를 모두 증가시켜주었다.
• rgBfs에서는 현재 색상과 이동할 곳의 색상이 같은 경우 외에도 현재 색상이 R이면 이동할 곳 색상이 G일 때, 현재 색상이 G이면 이동할 곳 색상이 R인 경우에도 deque에 삽입시켜주었다.

 

from collections import deque

n = int(input())
board = [list(input()) for _ in range(n)]
visit = [[0]*n for _ in range(n)]
rgVisit = [[0]*n for _ in range(n)]
count = 0
rgCount = 0
def bfs(y, x):
    global count, rgCount
    q = deque()
    q.append((y, x, board[y][x]))
    visit[y][x] = 1
    while q:
        nowy, nowx, nowchr = q.popleft()
        dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for y, x in dir:
            dy = nowy+y
            dx = nowx+x
            if 0 <= dy < n and 0 <= dx < n and nowchr == board[dy][dx] and visit[dy][dx] != 1:
                visit[dy][dx] = 1
                q.append((dy, dx, nowchr))
    if nowchr == 'B':
        count += 1
        rgCount += 1
    else:
        count += 1

def rgBfs(y, x):
    global rgCount
    rgQ = deque()
    rgQ.append((y, x, board[y][x]))
    rgVisit[y][x] = 1
    while rgQ:
        nowy, nowx, nowchr = rgQ.popleft()
        dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        for y, x in dir:
            dy = nowy + y
            dx = nowx + x
            if 0 <= dy < n and 0 <= dx < n and rgVisit[dy][dx] != 1:
                if nowchr == board[dy][dx]:
                    rgVisit[dy][dx] = 1
                    rgQ.append((dy, dx, nowchr))
                else:
                    if (nowchr == 'R' and board[dy][dx] == 'G') or (nowchr == 'G' and board[dy][dx] == 'R'):
                        rgVisit[dy][dx] = 1
                        rgQ.append((dy, dx, board[dy][dx]))
    rgCount += 1

for y in range(n):
    for x in range(n):
        if visit[y][x] != 1:
            bfs(y, x)
        if board[y][x] != 'B' and rgVisit[y][x] != 1:
            rgBfs(y, x)

print(count, rgCount)