백준 10026 적록색약 파이썬 풀이

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

10026번: 적록색약

1) 적록색약이 아닌 사람 : array를 바꿀 필요 없이 BFS로 총 구역이 몇개인지 구한다.

-> 어떻게 count를 하는가  ???가 또 관건인데... 

bfs에서 같은 문자가 계속 나오면 배열 c를 1로 표시를 해둔다. 그러면 이경우 R와 같은 위치에는 1이 나머지 배열은 아직 0이겠지요 ??

bfs1회 실행후 c의 상태 

이후 이중 for 문에서 if c[i][j] == 0: bfs 

배열 c[i][j] 값이 0이면 bfs를 다시 수행하게합니다!! 그리고 구역의 수는  bfs를 수행한 횟수와 같게 되겠지요

 

2) 적록색약인 사람 : R과 G를 같다고 생각하므로 R을 G로 바꾸어준 후에 bfs 탐색을 실행한다. 

 

#10026 적록색약
from collections import deque

n = int(input())
array = [list(map(str, input())) for _ in range(n)]

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
q = deque()
c = [[0]* n for _ in range(n)] # 0으로 n*n 2차원 배열 초기화

def bfs(x, y):
    q.append([x,y]) # current position
    c[x][y] = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if array[nx][ny] == array[x][y] and c[nx][ny] == 0:
                    q.append([nx, ny])
                    c[nx][ny] = 1

cnt = 0
for i in range(n):
    for j in range(n):
        if c[i][j] == 0:
            bfs(i, j)
            cnt += 1
print(cnt, end=' ')

# R==G이니까 R을 G로 바꿔주어 생각한다.

for i in range(n):
    for j in range(n):
        if array[i][j] == 'R':
            array[i][j] = 'G'
c = [[0]* n for _ in range(n)] # 0으로 n*n 2차원 배열 초기화
cnt = 0
for i in range(n):
    for j in range(n):
        if c[i][j] == 0:
            bfs(i, j)
            cnt += 1
print(cnt)