[백준] 10026번 : 적록색약 (python 파이썬)

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

10026번: 적록색약

문제 정리 : RGB로 이루어진 입력된 그림에 정상인이 본 색깔의 구역의 개수와 적록색약인 사람이 본 구역의 개수를 출력

 

from collections import deque
import sys
import copy
n = int(sys.stdin.readline().rstrip())
graph= []
d = [[1,0],[-1,0],[0,1],[0,-1],[0,0]] # 좌표 움직이는 방향

# n*n 크기의 그래프 입력받기
for i in range(n): 
    s = sys.stdin.readline().rstrip()
    graph.append(list(s))
        
red = 0 # r 구역 개수
green = 0 # g 구역 개수

#(0,0) 부터 (n,n) 까지 하나씩 확인 
for i in range(n):
    for j in range(n):
    
        if graph[i][j] == "R": # 현재 위치가 r인 경우 (r의 구역을 확인하고 "0"으로 바꾸기)
            q = deque() # 덱 생성
            q.append([i,j]) # 현재 위치 덱에 삽입
            
            while q: # 덱 안에 요소가 존재하는 동안 진행
                now = q.popleft() # 현재 위치 pop하기
                x = now[0] # x 추출 
                y = now[1] # y 추출
                for k in d: # 좌표의 이동 방향 차례대로 출력
                    nx = x + k[0] # x 위치 변경
                    ny = y + k[1] # y 위치 변경
                    if nx >= 0 and nx < n and  ny >= 0 and ny < n: # n*n 좌표 반경 안으로 위치가 변경되었을 때 실행되어야 한다.
                        if graph[nx][ny] == "R": # r 위치에서 이동했을 때에도 또 r인 경우
                            graph[nx][ny] = "0" # 현재 위치 0으로 바꾸기
                            q.append([nx,ny]) # 현재 위치 덱에 삽입
                          
            red = red+1 # graph[i][j]에서 시작하는 모든 r의 구역을 0으로 바꾸고 r의 구역 +1
            
        elif graph[i][j] == "G": # 현재 위치가 g인 경우 (g의 구역을 확인하고 "0"으로 바꾸기)
        	# 위의 경우와 같은 방법 수행
            q = deque()
            q.append([i,j])
            while q:
                now = q. popleft()
                x = now [0]
                y = now[1]
                for k in d:
                    nx = x + k[0]
                    ny = y + k[1]
                    if nx>= 0 and nx < n and ny >=0 and ny < n:
                        if graph[nx][ny] == "G":
                            graph[nx][ny] = "0"
                            q.append([nx,ny])
            green = green +1 # graph[i][j]에서 시작하는 모든 g의 구역을 0으로 바꾸고 g의 구역 +1

# 현재까지 r과 g의 구역은 각각 구해졌고, r과 g의 구역은 모두 "0"으로 대체 되었다. 남은 구역은 b(그래프에는 "0"과 b만 존재)
blue = 0 # b의 구역의 개수
zero = 0 # b의 구역을 제외한 남은 구역의 개수 (적녹색약의 경우에 필요하다)

#(0,0) 부터 (n,n) 까지 하나씩 확인 
for i in range(n): 
    for j in range(n):
        if graph[i][j] == "B":  # 현재 위치가 b인 경우 (b의 구역을 확인하고 "1"으로 바꾸기)
        #위의 경우와 똑같다 (0으로 바꾸는 걸 1로 바꾸는 것만 바뀐다)
            q = deque()
            q.append([i,j])
            while q:
                now = q.popleft()
                x = now[0]
                y = now[1]
                for k in d:
                    nx = x + k[0]
                    ny = y + k[1]
                    if nx >= 0 and nx < n and  ny >= 0 and ny < n:
                        if graph[nx][ny] == "B":
                            graph[nx][ny] = "1"
                            q.append([nx,ny])
            blue = blue+1
            
        elif graph[i][j] == "0": # 현재 위치가 "0" 인 경우 ("0"의 구역을 확인하고 "1"으로 바꾸기)
            #위의 경우와 똑같다 (0으로 바꾸는 걸 1로 바꾸는 것만 바뀐다)
            q = deque()
            q.append([i,j])
            while q:
                now = q.popleft()
                x = now[0]
                y = now[1]
                for k in d:
                    nx = x + k[0]
                    ny = y + k[1]
                    if nx >= 0 and nx < n and  ny >= 0 and ny < n:
                        if graph[nx][ny] == "0":
                            graph[nx][ny] = "1"
                            q.append([nx,ny])
            zero = zero+1

# 앞선 과정을 수행하면 r,g,b,zero 의 영역의 개수가 정해졌고, 그래프는 n*n 크기의 1만 존재하는 그래프로 바뀐다.
print(red+green+blue, blue+zero)

BFS를 수행하면서 우선 R과 G 구역의 개수를 구해야 한다. 굳이 R과 G의 구역을 확인하는 이유는 적녹색약이라는 경우가 존재하기 때문이다.

적록색약은 R과 G를 구별하지 못하므로 R과 G의 구역을 모두 "0"으로 만들어버려서 적록색약이 보는 그래프로 만들어 버리는 것이다.

 

따라서

1. 한번 그래프를 돌면서 R과 G의 구역의 개수를 각각 구하면서 동시에 그래프의 R과 G의 구역을 "0"으로 바꾼다.

2. 다음 다시 한번 그래프를 돌면서 남은 B의 구역의 개수를 구하면서, 동시에 적록색약이 보는 R과 G인 구역인 "0"(zero)의 구역의 개수를 구한다.

 

따라서 결과를 출력할 때, 정상인 경우(r+g+b), 적록색약인 경우(b+zero)를 수행한다.