10026번: 적록색약

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

 

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

from collections import deque, defaultdict

N = int(input())
MAP = []

RGB = defaultdict(list)
for n in range(N+2) :
    if n == 0 or n == N+1 :
        MAP.append('0'*(N+2))
        continue
    line = input()
    for idx, l in enumerate(line) :
        if l == 'R' :
            RGB['R'].append((n-1, idx))
        elif l == 'G' :
            RGB['G'].append((n-1, idx))
        else :
            RGB['B'].append((n-1, idx))
    line = '0' + line + '0'
    MAP.append(line)

# graph
X_graph = defaultdict(list) # 적록색약 아닌 사람
O_graph = defaultdict(list) # 적록색약인 사람
dx = [0, 0, -1, 1] # 상 하 좌 우
dy = [-1, 1, 0, 0] # 상 하 좌 우
for i in range(1, N+1) :
    for j in range(1, N+1) :
        now = MAP[i][j]
        now_is_red_or_green = now == 'R' or now == 'G'
        for idx in range(4) :
            new_i = i + dy[idx]
            new_j = j + dx[idx]

            if MAP[new_i][new_j] == now :
                # 적록색약 아닌 경우
                O_graph[(i-1, j-1)].append((new_i-1, new_j-1))
                # 적록색약인 경우
                X_graph[(i-1, j-1)].append((new_i-1, new_j-1))
            else :
                # 적록색약인 경우
                if now_is_red_or_green and (MAP[new_i][new_j] == 'R' or MAP[new_i][new_j] == 'G') :
                    O_graph[(i-1, j-1)].append((new_i-1, new_j-1))


# BFS
def BFS(start, num_group, graph, visited) :
    q = deque([start])
    visited[start[0]][start[1]] = 1

    while q :
        u = q.popleft()

        for v in graph[u] :
            if visited[v[0]][v[1]] == 0 :
                q.append(v)
                visited[v[0]][v[1]] = 1
    
    return num_group + 1

X_visited = [[0 for _ in range(N)] for _ in range(N)]
O_visited = [[0 for _ in range(N)] for _ in range(N)]

X_num_group = 0
O_num_group = 0

for rgb in ['R', 'G', 'B'] :
    for item in RGB[rgb] :
        if X_visited[item[0]][item[1]] == 0 :
            X_num_group = BFS(item, X_num_group, X_graph, X_visited)
        if O_visited[item[0]][item[1]] == 0 :
            O_num_group = BFS(item, O_num_group, O_graph, O_visited)
print(X_num_group, O_num_group)

 

아이디어

1. RGB에 따라 위치를 저장하는 dictionary로 start 위치를 지정한다.
2. 적록색약인 사람을 위한 graph, 적록색약이 아닌 사람을 위한 graph를 각각 저장한다.
3. 적록색약인 사람과 아닌 사람에 따라 달라지는 탐색 방법(BFS)을 구현한다.
4. 적록색약인 사람이 인식하는 블럭 단위를 계산하는 변수와, 아닌 사람이 인식하는 변수를 각각 지정하고 따로 저장한다.