[Python/백준] 10026 적록색약

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

10026번: 적록색약

<문제 해설>

DFS탐색 문제이다. 

1. 구역들을 입력받아서 2차원 배열로 만든다.
2. 우선 적록색약이 아닌 사람이 보는 구역들을 구하기 위해서 R,B,G를 따로 DFS로 탐색한다.
3. 2번을 진행하는 동안 R과 G는 0으로 교체, B는 1로 교체한다. 적록색약인 사람이 보는 구역들을 구하기 위해서 이다.
4. 0,1을 구분으로 구역이 몇개로 나누어져 있는지 DFS로 탐색한다.
5. 4번에서 탐색한 지역은 2로 교체해서 탐색한 위치라는 걸 기록한다.
6. 2번에서 계산한 적록색약이 아닌 사람이 본 구역과 4번에서 계산한 적록색약인 사람이 본 구역을 출력한다.

<예시>

사진 1

사진 1은 입력 받았을 때 2차원 배열의 모습니다.

빨간색이 칠해진곳 0으로 변경, 파란색 1로 변경, 초록색을 0으로 변경해서 적록색 아닌 구역이 4로 계산되며 사진 2로 변환된다.

사진 2

사진 2는 적록색맹이 구분할 수 없는 뜻인 노란색 지역(0)과 파란색지역(1)로 구분되어 적록색맥인 사람은 3개의 구역으로 본다. 구역을 탐색한 곳은 2로 변환되어 사진 3처럼 변한

사진 3

적록색 아닌 구역 출력하고 적록색 구역도 출력한다.

<코드>

def DFS_B_RG(Node):
    for mv in Move:
        y = mv[0] + Node[0]
        x = mv[1] + Node[1]
        if 0 <= x < N and 0 <= y < N:
            if Picture[y][x] == Check:
                Picture[y][x] = Number
                DFS_B_RG([y,x])
                
import sys
sys.setrecursionlimit(10**7)

N = int(sys.stdin.readline())

Picture = []
Move = [[1,0],[-1,0],[0,1],[0,-1]]
for n in range(N):
    Picture.append(list(sys.stdin.readline().rstrip()))
    
Healthy = 0
C_Weak = 0
for n in range(N):
    for m in range(N):
        if Picture[n][m] != 1 and Picture[n][m] != 0:
            Healthy += 1
            Check = Picture[n][m]
            if Check == 'B':
                Number = 1
            else:
                Number = 0
            Picture[n][m] = Number
            DFS_B_RG([n,m])
            
for n in range(N):
    for m in range(N):
        if Picture[n][m] != 2:
            C_Weak += 1
            Check = Picture[n][m]
            Number = 2
            Picture[n][m] = Number
            DFS_B_RG([n,m])
            
print(Healthy,C_Weak)

<코드 설명>

def DFS_B_RG(Node): //DFS탐색하는 함수
    for mv in Move: //노드를 움직일 수 있게 도와주는 배열
        y = mv[0] + Node[0] //노드를 상하좌우로 1씩 움직여 보면서
        x = mv[1] + Node[1]
        if 0 <= x < N and 0 <= y < N: //2차원 배열 밖으로 나가지 않았다면
            if Picture[y][x] == Check: //찾고 있는 구역이 맞다면
                Picture[y][x] = Number //표시해야하는 숫자로 교체하고
                DFS_B_RG([y,x]) //재귀함수 호출한다.
                
import sys //sys함수 호출
sys.setrecursionlimit(10**7) //재귀 제한 해제

N = int(sys.stdin.readline()) //int로 N값 입력받기

Picture = [] //구역을 저장할 2차원 배열
Move = [[1,0],[-1,0],[0,1],[0,-1]] //상하좌우로 1씩 이동
for n in range(N): //N만큼 반복하면서
    Picture.append(list(sys.stdin.readline().rstrip())) //구역을 1줄씩 받아온다.
    
Healthy = 0 //건강한 사람이 보는 구역을 기록할 함수 0으로 초기화
C_Weak = 0 //적록색약인 사람이 보는 구역을 기록할 함수 0으로 초기화
for n in range(N): //N만큼 반복하면서(y축 탐색)
    for m in range(N): //N만큼 반복하면서(x축 탐색)
        if Picture[n][m] != 1 and Picture[n][m] != 0: //탐색한 구역이 아니라면
            Healthy += 1 //건강한 사람이 보는 구역 1추가
            Check = Picture[n][m] //어떤 색을 탐색하는 중인지 Check에 저장해서 DFS탐색할 때 저장된 색만 탐색되게 함
            if Check == 'B': //색이 B라면
                Number = 1 //탐색한 지역을 1로 교체
            else:
                Number = 0 //색이 R,G라면 
            Picture[n][m] = Number //탐색한 지역을 0으로 교체
            DFS_B_RG([n,m]) //함수 호출
            
for n in range(N): //위와 같음
    for m in range(N): //위와 같음
        if Picture[n][m] != 2: //탐색한 지역이 아니라면
            C_Weak += 1 //적록색약인 사람이 보는 구역 1추가
            Check = Picture[n][m] //보는 구역이 어디인지 표시
            Number = 2 //교체할 값
            Picture[n][m] = Number //탐색한 지역을 2로 교체
            DFS_B_RG([n,m]) //함수 호출
             
print(Healthy,C_Weak) //건강한 사람, 적록색약인 사람 순으로 출력