10026번 - 적록색약

💡 bfs 새로운 유형 (입력값이 숫자가 아님)

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
graph = []
normal_cnt = 0
special_cnt = 0

for _ in range(N):
    graph.append(list(input().rstrip()))

def bfs(a, b, color, is_special):
    
    dq = deque()
    dq.append((a,b,color))    
    visited[b][a] = True

    # 상 하 좌 우
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]
    
    while dq:
        x ,y, color = dq.popleft()
        for idx in range(4):
            nx = x + dx[idx]
            ny = y + dy[idx]
            if 0 <= nx < N and 0 <= ny < N and visited[ny][nx] is False:
                # 일반인 경우
                if is_special == False and color == graph[ny][nx]: 
                    dq.append((nx,ny,graph[ny][nx]))
                # 적록색약인 경우
                elif is_special == True and (color in ['R','G'] and graph[ny][nx] in ['R','G']):
                    dq.append((nx,ny,graph[ny][nx]))
                elif is_special == True and color == 'B' and color == graph[ny][nx]:
                    dq.append((nx,ny,graph[ny][nx]))
                else:
                    continue

                visited[ny][nx] = True
                    
                
visited = [[False] * N for _ in range(N)]

# 일반은 빨, 초, 파
for i in range(N):
    for j in range(N):
        if visited[i][j] == False:
            bfs(j, i, graph[i][j], False)
            normal_cnt += 1

visited = [[False] * N for _ in range(N)]

# 적록 색약은 빨(R) == 초(G), 파
for i in range(N):
    for j in range(N):
        if visited[i][j] == False:
            bfs(j, i, graph[i][j], True)
            special_cnt += 1

print(normal_cnt, special_cnt)

• 위 문제는 기존의 bfs와 접근은 같지만, 입력이 숫자형식이 아니고, 경우의 수가 R,B,G 총 3가지가 존재하였다.
• 또한 일반인의 경우에는 RGB이고, 적록색약의 경우에는 RB이기 떄문에, 2가지 케이스를 나눠서 진행하였다.
• bfs에 넣어줄 때, bfs()를 하나만 만들고, is_special를 통해서 적록색약인지 아닌지를 판단해서 넣어주었다.
• visited 배열을 일반을 거치고 나서 한번 더 초기화 해주었는데, 생각해보니 Visited배열을 숫자로 선언하고, 일반일 경우에는 0 -> 1, 적록색약일 경우에는 1 -> 2 로 가도록 하면 visited 배열을 한번 더 초기화할 필요가 없었을거 같다.

💡 코테 스터디에서 나온 기발한 풀이법

우진

elif is_special == True and (color in 'RG'and graph[ny][nx] in 'RG'):

• 위 코드와 같이 문자열로 'RG'로 선언해도 R과 G를 따로 보고 판단한다.
• 이 방식이 기존 나의 방식에서는 배열을 선언해서 했던 방식보다 메모리 적인 측면에서 더 좋을거 같다고 생각하였다.