[ 그래프 이론-10026 ] 적록색약(Python)

---

접근법

기본적인 아이디어는 DFS를 생각했고, 여기서 특이점은 R,G를 동일하게 인식해야 한다는 점이다.

따라서 DFS를 적용할 때 B가 아닌 위치를 다른 배열에 체크해 둔 후, 해당 배열에 한번 더 DFS를 적용하여 적록색약인 경우에 구역의 수를 계산 하였다.

---

정답

import sys
sys.setrecursionlimit(10**9)
dx = [0,0,-1,1]
dy = [-1,1,0,0]

N = int(input())

def dfs(x,y,color):
    image[y][x] = 0
    if color != "B":
        check[y][x] = 1
    
    for i in range(4):
        X = x + dx[i]
        Y = y + dy[i]
        if(0 <= X < N and 0 <= Y < N):
            if image[Y][X] == color:
                image[Y][X] = 0
                dfs(X,Y,color)
                
def dfs2(x,y):
    check[y][x] = 0
   
    for i in range(4):
        X = x + dx[i]
        Y = y + dy[i]
        if(0 <= X < N and 0 <= Y < N):
            if check[Y][X] == 1:
                check[Y][X] = 0
                dfs2(X,Y)

image = []

for _ in range(N):
    img = list(sys.stdin.readline().rstrip())   
    image.append(img)
    
check = [[0]*N for _ in range(N)]

normal = 0
notnormal = 0

for y in range(N):
    for x in range(N):
        if image[y][x] != 0:
            normal += 1
            if image[y][x] == "B":
                notnormal += 1
            dfs(x,y,image[y][x])

for y in range(N):
    for x in range(N):
        if check[y][x] == 1:
            notnormal += 1
            dfs2(x,y)
            
print(normal, notnormal)

 

dfs의 기본적인 틀은 백준-1260번에서 구현한 dfs를 들고 왔다.

def dfs(x,y,color):
    image[y][x] = 0
    if color != "B":
        check[y][x] = 1
    
    for i in range(4):
        X = x + dx[i]
        Y = y + dy[i]
        if(0 <= X < N and 0 <= Y < N):
            if image[Y][X] == color:
                image[Y][X] = 0
                dfs(X,Y,color)

 

image에는 입력받은 "R","G","B"의 값들이 이차원 배열에 저장되어 있다. 

방문했음을 확인하기 위해 dfs의 인자로 받은 위치의 값을 0으로 바꾼 후 "B"가 아닌 경우 check 2차원 배열에서 해당 위치를 1로 설정한다. 적록색약의 경우 "R","G"를 같은 색으로 인식하기 때문에 해당 위치만 1로 설정하여 dfs를 한번 더 돌리기 위해서다.

이후 dx, dy만큼 변화를 줘 상/하/좌/우에 같은 색이 있는 경우 해당 위치를 계속 방문함으로써 dfs를 재귀적으로 구현하였다.

def dfs2(x,y):
    check[y][x] = 0
   
    for i in range(4):
        X = x + dx[i]
        Y = y + dy[i]
        if(0 <= X < N and 0 <= Y < N):
            if check[Y][X] == 1:
                check[Y][X] = 0
                dfs2(X,Y)

 

dfs2의 경우 적록색약을 위해 dfs()를 customize 하였다.

"R","G"의 위치만 1이기 때문에 인자로 받아온 위치의 값을 0으로 설정하여 방문했음을 확인한다.

이후 dx, dy만큼 변화를 줘 상/하/좌/우에 1인 위치를 계속 방문함으로써 dfs2를 재귀적으로 구현하였다.

check = [[0]*N for _ in range(N)]

normal = 0
notnormal = 0

for y in range(N):
    for x in range(N):
        if image[y][x] != 0:
            normal += 1
            if image[y][x] == "B":
                notnormal += 1
            dfs(x,y,image[y][x])

for y in range(N):
    for x in range(N):
        if check[y][x] == 1:
            notnormal += 1
            dfs2(x,y)
            
print(normal, notnormal)

 

입력받은 image의 크기만큼 2중 for문을 돌면서 image가 0이 아닌 경우 normal를 증가시켜 새로운 구역임을 확인하고 dfs()의 인자로 해당 위치와 색을 넣는다. 이때, 색이 "B"인 경우에만 notnormal도 증가시킨다. "R","G"를 구분하지 못하므로 추가적으로 "B"구분에 대한 계산을 줄이기 위함이다.

 

이후 다시 2중 for문을 돌면서 check 값이 1인 경우 notnormal를 증가시키고 dfs2의 인자로 넣는다.