[백준] 10026 - 적록색약

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

10026번: 적록색약

문제 한줄 이해

-R, G, B로 이루어진 그래프가 있을때 적록색약을 가지고 있는 사람은 R과 G를 차이를 거의 느끼지 못해 그래프를 볼때 같은 구역이라 생각한다. 이때 적록색약이 있는 사람과 없는 사람이 그래프를 볼때 나뉘어지는 구역 수 출력

 

생각난 풀이

1번째 방법: 그래프를 BFS를 통해 구역을 나누면서 탐색하는 방법이 떠올랐다.

적록색약이 없는 경우 단순히 탐색을 진행

적록색약이 있는 경우 R과 G를 같은 취급

import sys
from collections import deque
N = int(sys.stdin.readline())
graph = []
for i in range(N):
    graph.append(list(map(str, sys.stdin.readline().rstrip())))
    
# 들어오는 색깔은 target1 과 target2 받는다.
def color(x,y,target1,target2):
    que = deque()
    que.append((x,y))
    visited[x][y] = True
        
    while que:
        nowx, nowy = que.popleft()
        
        dx = [0,0,1,-1]
        dy = [1,-1,0,0]
        
        for i in range(4):
            nextx = dx[i] + nowx
            nexty = dy[i] + nowy
            if nextx >= 0 and nexty >= 0 and nextx <=N-1 and nexty <= N-1:
                if (graph[nextx][nexty] == target1 or graph[nextx][nexty] == target2) and visited[nextx][nexty] == False:
                    visited[nextx][nexty] = True
                    que.append((nextx,nexty))
for k in range(2):
    cnt = 0
    visited = [[False for i in range(N)] for i in range(N)]
    for i in range(N):
        for j in range(N):
            # k=0 일때는 정상인의 경우
            if k == 0:
                if visited[i][j] == False:
                    color(i,j,graph[i][j],graph[i][j])
                    cnt +=1
            # 적록색약이 있는 경우
            elif k == 1:
                if visited[i][j] == False:
                    # 색깔이 R이나 G일경우 매개변수를 R과 G를 넘겨준다.
                    if graph[i][j] == 'R' or graph[i][j] == 'G':
                        color(i,j,"R","G")
                    elif graph[i][j]=="B":
                        color(i,j,graph[i][j],graph[i][j])
                    cnt +=1
    print(cnt,end=' ')
print()