[Python] 적록색약 - 백준 (BFS)

해당 글은 백준 10026번 문제 '적록색약'을 다룬다.

문제

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

10026번: 적록색약

 

설명

해당 문제는 DFS/BFS로 풀 수 있는 문제이고, 해당 글에서는 BFS로 해결하였다.

BFS의 파라미터로 flag를 받아 그에 따라 적록색약인지 아닌지를 구별하여 if문으로 구분하였다.

적록색약인 경우(flag=1)는 아래의 조건문으로 코드를 구현하였다.

if flag == 1 and 
	(arr[x][y] == arr[nx][ny] or 
	(arr[x][y] == 'R' and arr[nx][ny] == 'G') or (arr[x][y] == 'G' and arr[nx][ny] == 'R')):

 

코드

from collections import deque
n = int(input())
arr = [input() for _ in range(n)]

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

def bfs(flag):
    visited = [[0]*n for _ in range(n)]
    count = 0
    for i in range(n):
        for j in range(n):
            if visited[i][j]:
                continue
            count += 1
            visited[i][j] = count
            q = deque([])
            q.append((i, j))
            while q:
                x, y = q.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if nx >= 0 and nx < n and ny >= 0 and ny < n and visited[nx][ny] == 0:
                        if flag == 0 and arr[x][y] == arr[nx][ny]:
                            q.append((nx, ny))
                            visited[nx][ny] = count
                        if flag == 1 and (arr[x][y] == arr[nx][ny] or (arr[x][y] == 'R' and arr[nx][ny] == 'G') or (arr[x][y] == 'G' and arr[nx][ny] == 'R')):
                            q.append((nx, ny))
                            visited[nx][ny] = count
    return max(map(max, visited))

print(bfs(0), bfs(1))