적록색약

10026번: 적록색약

 

나의 풀이

from collections import deque
import copy
import sys
input = sys.stdin.readline
n = int(input())

# n_type = 0 (색맹 아님)
# n_type = 1 (색맹)
def color_group(now_map, n_type):
    answer = 0
    for i in range(n):
        for j in range(n):
            if now_map[i][j] != 1:
                answer += 1
                queue = deque([(i,j)])
                n_color = now_map[i][j]
                now_map[i][j] = 1
            
                while queue:
                    a, b = queue.popleft()
                    for m_a, m_b in ((1,0),(-1,0),(0,1),(0,-1)):
                        n_a, n_b = a+m_a, b+m_b
                        if (0 <= n_a < n) and (0 <= n_b < n):
                            if (n_type == 0):
                                if (now_map[n_a][n_b] == n_color):
                                    now_map[n_a][n_b] = 1
                                    queue.append((n_a, n_b))
                            else:
                                if (n_color == 'B'):
                                    if (now_map[n_a][n_b] == n_color):
                                        now_map[n_a][n_b] = 1
                                        queue.append((n_a, n_b))
                                else:
                                    if (now_map[n_a][n_b] in ('R','G')):
                                        now_map[n_a][n_b] = 1
                                        queue.append((n_a, n_b))
    return answer
    

map_list = []
for _ in range(n):
    map_list.append(list(input().rstrip()))
first = color_group(copy.deepcopy(map_list), 0)
second = color_group(copy.deepcopy(map_list), 1)
print(f"{first} {second}")

 

시간 복잡도

bfs 탐색으로 색약 그룹을 카운트 하므로 ( 이차형 시간 복잡도 )
해당 알고리즘 시간 복잡도는 : 이차형 시간 복잡도 ( O(n**2) )