백준 10026 적록색약

문제

적록색약

적록색약인 사람과 아닌 사람이 보는 구역의 개수를 구하자

난이도 : Gold5

---

풀이

1. 적록색약과 아닌 사람을 따로 놓고 bfs를 수행

---

코드

import sys
from collections import deque
from copy import deepcopy

N = int(sys.stdin.readline())
RGB = [list(sys.stdin.readline().strip()) for _ in range(N)]
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
visited = [[False for _ in range(N)] for _ in range(N)]
visited_RG = [[False for _ in range(N)] for _ in range(N)]
count = 0; count_RG = 0

RGB_copy = deepcopy(RGB)  # 적록색약 bfs를 위해 R, G를 모두 G로 통일
for i in range(N):
    for j in range(N):
        if RGB[i][j] == 'R':
            RGB_copy[i][j] = 'G'
    

def bfs(x, y, color):
    global count
    q = deque([(x, y)])
    visited[x][y] = True  # 시작점 방문 체크
    
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + directions[i][0]
            nc = c + directions[i][1]
            if 0 <= nr < N and 0 <= nc < N and not visited[nr][nc] and RGB[nr][nc] == color:  # 현재 지점의 색상과, 인근(nr, nc) 색상이 같을 때
                q.append((nr, nc))
                visited[nr][nc] = True  # 조건에 부합하면 visited를 True로 변환 (어차피 큐에 append 해놓아서 True로 변환해도 방문함)
                
    count += 1
    

def bfs_RG(x, y, color):
    global count_RG
    q = deque([(x, y)])
    visited_RG[x][y] = True
    
    while q:
        r, c = q.popleft()
        for i in range(4):
            nr = r + directions[i][0]
            nc = c + directions[i][1]
            if 0 <= nr < N and 0 <= nc < N and not visited_RG[nr][nc] and RGB_copy[nr][nc] == color:
                q.append((nr, nc))
                visited_RG[nr][nc] = True
                
    count_RG += 1
    

for j in range(N):
    for i in range(N):
        if not visited[i][j]:
            bfs(i, j, RGB[i][j])  # 좌표와 현재 색상을 인자로 넘김, 현재 
        if not visited_RG[i][j]:
            bfs_RG(i, j, RGB_copy[i][j])

print(count, count_RG)

---

결과

기존에는 시작 지점을 찾는 함수를 만들고, 매 시작 지점을 bfs의 인자로 넘겨 주었다.
하지만 지금과 같은 문제처럼 RGB 세 개의 포인트가 있으면 매번 찾는게 상당히 비효율적이다.
따라서 visited 리스트 만들고, 모든 지점을 방문하되 방문했으면 main에서도 방문 안 하도록 코드 작성해야 한다.