[Python 3] BOJ - 10026 "적록 색약"

 # 문제 링크 : https://www.acmicpc.net/problem/10026

10026번: 적록색약

 

 # 풀이 :

 이 문제는 단순히 BFS를 실행하면 되는 문제이다. 4방향으로 인접하면 같기 때문에 큐에 좌표를 넣고 행렬의 범위를 벗어나지 않고 적힌 글자가 같다면 그룹 번호를 갱신해주면 된다. 다만, 적록색약의 경우는 R과 G를 같다고 처리해주면 정답을 구할 수 있다.

 

 # 코드

import sys, collections
dx = [0,1,0,-1]
dy = [1,0,-1,0]
n = int(sys.stdin.readline())

# group : 해당 위치를 방문했는지 안했는지 체크하는 2차원 배열
group = [[False] * n for _ in range(n)]

# board : 문제에서 주어지는 그리드의 상태
board = [list(sys.stdin.readline().rstrip()) for _ in range(n)]

# bfs : 인접한 블록을 같은 구역으로 나눠주는 함수
def bfs(r, c):
    q = collections.deque()
    q.append((r,c))
    group[r][c] = True
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if group[nx][ny] == False and board[r][c] == board[nx][ny]:
                    group[nx][ny] = group[x][y]
                    q.append((nx, ny))

# init : group을 초기화 시켜주는 함수
def init(c):
    for i in range(n):
        for j in range(n):
            c[i][j] = False

# normal : 정상인이 보는 그룹의 총 갯수
# abnormal : 색약인이 보는 그룹의 총 갯수
normal = 0
abnormal = 0

# 정상인의 경우 먼저 bfs 수행
for i in range(n):
    for j in range(n):
        # 아직 방문하지 않았다면 bfs
        if group[i][j] == False:
            normal += 1
            bfs(i,j)

# group 초기화
init(group)

# 색약인의 경우, 그리드 상태 변경
for i in range(n):
    for j in range(n):
        if board[i][j] == 'R':
            board[i][j] = 'G'

# 색약인의 경우 bfs 수행
for i in range(n):
    for j in range(n):
        if group[i][j] == False:
            abnormal += 1
            bfs(i, j)

# 정답 출력
print(normal, abnormal)