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

 

문제

 

10026번: 적록색약

 

 

풀이 (Python)

 

import sys
sys.setrecursionlimit(10 ** 6)          # 메모리 초과 방지 


n=int(input())
arr=[]
count=0
blindness_count=0
for _ in range(n):arr.append(list(input())) 

visited=[[False for i in range(n)] for j in range(n)]       # 방문 여부 체크 리스트


def dfs(color,y,x,mode):    # 전 탐색위치의 색깔과 같으면 진행 아닌 경우 종료 
    global count
    if mode=="normal":              # 적록색약이 아닌경우 + 전 dfs에서 입력받은 color와 다른 경우
        if color!=arr[y][x]:return
    else:                            # 적록색약이면서 + 전 dfs에서 입력받은 color와 다른 경우
        if arr[y][x]=="R" or arr[y][x]=="G":   
            if color=="B":return
        else:
            if color!="B":return
            

    visited[y][x]=True  # 방문 처리

    dx=[-1,1,0,0]   # dx,dy활용으로 상하좌우탐색
    dy=[0,0,1,-1]
    


    
    for i in range(4):          
        nx,ny=x+dx[i],y+dy[i]
        if nx>=0 and nx<n and ny>=0 and ny<n:   #범위 확인
            if not visited[ny][nx]:
                dfs(color,ny,nx,mode)


for i in range(n):                  
    for j in range(n):
        if not visited[i][j]:   # 방문하지 않은 좌표를 기준으로 모든 좌표 탐색
            dfs(arr[i][j],i,j,"normal")     #적록색약이 아닌 경우
            count+=1


visited=[[False for i in range(n)] for j in range(n)]   # 방문 여부 초기화



for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            dfs(arr[i][j],i,j,"blind")  # 적록색약인 경우 
            blindness_count+=1
        


print(count,blindness_count)

 

설명  (Python)

 

Point 1)  dx와 dy를 활용하여 상하좌우 탐색

 

    dx=[1,-1,0,0]               # 방향 선택
    dy=[0,0,1,-1]

 

위의 dx, dy와 현재 x, y값이 있다면 for문을 통해 간단하게 상하좌우를 검사할 수 있다.

이와 같은 로직을 모르는 경우 if ~~~~ x4 if문을 4번을 사용하여 검사하기 때문에 가독성이 떨어지고, 코드가 길어진다.

하지만 위의 dx, dy를 활용하는 경우 아래와 같이 간결하게 표현이 가능하다.

 

for i in range(4):
    nx,ny=x+dx[i],y+dy[i]   # i값 변화에 대해 x, y값 상하좌우 변동

 

Point 2)  DFS함수

 

def dfs(color,y,x,mode):    # 전 탐색위치의 색깔과 같으면 진행 아닌 경우 종료 
    global count
    if mode=="normal":              # 적록색약이 아닌경우 + 전 dfs에서 입력받은 color와 다른 경우
        if color!=arr[y][x]:return
    else:                            # 적록색약이면서 + 전 dfs에서 입력받은 color와 다른 경우
        if arr[y][x]=="R" or arr[y][x]=="G":   
            if color=="B":return
        else:
            if color!="B":return
            

    visited[y][x]=True  # 방문 처리

    dx=[-1,1,0,0]   # dx,dy활용으로 상하좌우탐색
    dy=[0,0,1,-1]
    


    
    for i in range(4):          
        nx,ny=x+dx[i],y+dy[i]
        if nx>=0 and nx<n and ny>=0 and ny<n:   #범위 확인
            if not visited[ny][nx]:
                dfs(color,ny,nx,mode)

 

mode 매개변 추가하여 한 dfs함수에서 2가지의 방식으로 적록색약인 경우와 적록색약이 아닌경우 2가지 모두 작동하게 작성하였다.

 

    if mode=="normal":              # 적록색약이 아닌경우 + 전 dfs에서 입력받은 color와 다른 경우
        if color!=arr[y][x]:return
    else:                            # 적록색약이면서 + 전 dfs에서 입력받은 color와 다른 경우
        if arr[y][x]=="R" or arr[y][x]=="G":   
            if color=="B":return
        else:
            if color!="B":return

color를 전 dfs가 탐색하는 좌표의 color값을 전달받기 때문에 

if문을 통해 color와 현 arr [y][x]의 색을 비교하여 판단한다.

이때 적록색약이 아닌 경우 arr [y][x]="R"와 arr [y][x]="G"을 둘 다 R로 생각하여 풀이하였다.

 

 

Point 3) 런타임에러( RecursionError )

 

파이썬 같은 경우 재귀함수를 사용할 때 재귀 깊이가 1000밖에 되지 않는다. 그러므로 웬만한 재귀를 사용하는 완전탐색 or dfs에서 런타임에러( RecursionError )가 자주 발생하게 된다.

이때 해결 방법으로 재귀깊이를 강제로 늘리는 방법이 있다.

import sys
sys.setrecursionlimit(10 ** 6)          # 메모리 초과 방지

필자의 경우 백준 문제를 푸는 과정에서 재귀를 사용하는 경우, 일단 위의 코드를 작성하고 보는 편이다.

처음 런타임에러( RecursionError )를 접하는 경우, 코드에서 문제가 있다고 판단해 많은 시간을 날리기 쉬운데 

sys라이브러리를 활용하여 간단하게 해결할 수 있기에 알아두는 것이 좋을 것이다.