[BOJ-10026] 적록색약

 

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

10026번: 적록색약

---

[풀이]

전형적인 BFS, DFS 활용 문제이다.

여기서 주의해야되는게

정상인이 볼 수 있는 구역의 개수와

적록색약인 사람이 볼 수 있는 구역의 개수를 따로 고려해야한다는 것이다.

 

즉, 정상인이 볼 수 있는 초록색구역의 개수를 뺀값이 적록색약인 사람이 볼 수 있는 구역의 개수로 간주하면 완된다.

(처음에 이렇게 시도했으나 틀렸다는 결과가 나왔다.)

 

그래서 두개의 딕셔너리를 먼저 만든다.

(1) 정상인(NORMAL_AREA)

Key 값: R, G, B

Value 값: 구역의 개수

 

(2) 적록색약인(NOT_GREEN)

Key 값: R, B

Value 값: 구역의 개수

 

(3) 정상인이 볼 수 있는 구역의 개수 구하기

일반적인 BFS 문제풀이로 하면 된다

 

정상인이 볼 수 있는 구역개수 카운트를 다끝나면

적록색약인이 볼 수 있는 구역개수 카운트를 위해서 방문리스트(visited)를 모두 False로 초기화시킨다.

 

(4) 적록색약인이 볼 수 있는 구역의 개수 구하기

(1-a) 현재위치가 'R' 이거나 'G'라면

-> BFS탐색 -> 'R' 구역의 개수를 카운트(NOT_GREEN['R']+=1)

 

(1-b) 현재위치가 'B'라면

-> BFS탐색 -> 'B'구역의 개수를 카운트하고 (NOT_GREEN['B']+=1)

 

이제 적록색약인일때 BFS연산을 알아보자

두번의 BFS함수를 만들 수 있지만, 굳이 그럴 필요 없어서

적록색약인읠 위한 BFS연산인지 확인하는 flag(not_green)를 넣었다.

 

(2-a) 현재위치(y,x)가 'R'이나 'G'인 경우

현재위치의 상/하/좌/우인 다음 위치 (nexty, nextx)가 'R', 'G'이라면 계속 큐에 넣는다.

단, 다음위치가 아직 방문하지 않은 상태여야한다.

 

(2-b) 현재위치(y,x)가 'B'인 경우

현재위치의 상/하/좌/우인 다음 위치(nexty, nextx)가 'B'라면 계속 큐에 넣는다.

단, 다음위치가 아직 방문하지 않은 상태여야한다.

---

[코드]

import sys
from collections import deque
input= sys.stdin.readline
q=deque()

#입력#
N= int(input())
MAP=[ [*input().strip()] for _ in range(N)]

NORMAL_AREA={'R':0, 'G':0, 'B':0} #정상인
NOT_GREEN={'R': 0, 'B':0}#적록색약
visited=[ [False]*N for _ in range(N) ]

#상/하/좌/우
dy=(-1,1,0,0)
dx=(0,0,-1,1)

def isRange(y,x):
    if (y>=0 and y<N) and (x>=0 and x<N):
        return True
    return False

def bfs(flag):
    not_green=flag
    while q:
        cury, curx=q.popleft()
        #현재 위치 아직 방문안한 상태라면
        if not visited[cury][curx]:
            visited[cury][curx]=True #방문
            for i in range(4):
                nexty=cury+dy[i]
                nextx=curx+dx[i]
                
                #현위치의 상/하/좌/우 가 적절한 위치인가?
                if isRange(nexty, nextx):
                    #정상인#
                    if not not_green:
                        #현위치의 상/하/좌/우가 현위치값과 동일하고, 아직 방문안한 상태인가?
                        if (MAP[nexty][nextx]==MAP[cury][curx]) and (not visited[nexty][nextx]):
                            q.append((nexty, nextx))
                            
                    #적록색약#
                    else:
                        #현위치값이 R/G이고, 현위치의 상/하/좌/우 값이 R/G이고 아직 방문 안한 상태인가?
                        if (MAP[cury][curx]=='R' or MAP[cury][curx]=='G') and (MAP[nexty][nextx]=='R' or MAP[nexty][nextx]=='G') and (not visited[nexty][nextx]):
                            q.append((nexty, nextx))

                        #현재위치값이 B이고, 현위치의 상/하/좌/우 값이 B라면
                        elif (MAP[cury][curx]=='B') and (MAP[nexty][nextx]==MAP[cury][curx]) and (not visited[nexty][nextx]):
                            q.append((nexty, nextx))
                        
#정상인#
for y in range(N):
    for x in range(N):
        #아직 방문하지 않은 상태라면
        if not visited[y][x]:
            #BFS 연산을하여 구역개수 카운트
            q.append((y,x))
            bfs(flag=False)
            #MAP[y][x]값( R/G/B) 에 따른 NORMAL_AREA 카운트
            NORMAL_AREA[MAP[y][x]]+=1

#적록색약#
visited=[ [False]*N for _ in range(N) ]
for y in range(N):
    for x in range(N):
        if not visited[y][x]:
            q.append((y,x))
            bfs(flag=True)
            if MAP[y][x]=='R' or MAP[y][x]=='G':
                NOT_GREEN['R']+=1
            else:#'B'
                NOT_GREEN[MAP[y][x]]+=1

#정상인 사람은 세구역 모두 본다.
#적록색약인 사람은 초록색 구역을 제외한 나머지만 본다.
print('{} {}'.format(sum(NORMAL_AREA.values()),  sum(NOT_GREEN.values())))