[Python] 10026 - Baekjoon

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

이 문제는 두가지로 나누어 설정해야하는 문제다.

적록색맹이라면 R, G를 같은 값으로 묶어야한다는 점! 반대로 말하면 B가 아니면 된다는 말이다.

 

BFS로 풀면 진짜 별 타격없이 풀었겠지만

DFS로 풀어보고싶었고 연습을 하는게 좋다고 판단하여 DFS로 풀어봤다.

근데 아래의 그림처럼 지속적으로 RecursionError가 나오는 바람에... 

이 부분을 어떻게 해결해야하나....

 

import sys
sys.setrecursionlimit(10**6)

n = int(input())

graph = []
for _ in range(n):
    graph.append(list(input()))

visited = [[False] * n for _ in range(n)]
dx = [1,-1,0,0]
dy = [0,0,-1,1]

def dfs(x,y,c):
    visited[x][y] = True
    for i in range(4):
        ax = x + dx[i]
        ay = y + dy[i]
        if 0 <= ax < n and 0<= ay < n and visited[ax][ay] == False and c == graph[ax][ay]:
            dfs(ax,ay,graph[ax][ay])
    return 0
result = 0
for i in range(n):
    for j in range(n):
        if visited[i][j] == False:
            dfs(i,j,graph[i][j])
            result += 1
print(result, end=" ")

def dfs_r(x,y,c):
    visited[x][y] = True
    for i in range(4):
        ax = x + dx[i]
        ay = y + dy[i]
        if 0 <= ax < n and 0 <= ay < n and visited[ax][ay] == False and (c == graph[ax][ay] or (c != "B" and graph[ax][ay] != "B")):
            dfs_r(ax,ay,graph[ax][ay])
    return 0

visited = [[False] * n for _ in range(n)]
result = 0
for i in range(n):
    for j in range(n):
        if visited[i][j] == False:
            dfs_r(i,j,graph[i][j])
            result += 1
print(result)

 

그리고 왜 이런 일이 발생하는가.. 생각해봤는데 RecursionError는 재귀함수의 깊이가 너무 깊어져서 나온 에러니까

이 에러를 어떻게 바꿔야하나? 싶었는데 문제가 128MB를 추구하니까 재귀의 깊이를 늘려도 괜찮겠다싶었다.

import sys

sys.setrecursionlimit(10**6)

을 작성해주었다.

진짜 이 두 줄이면 해결됐는데 나는 새롭게 써보는 코드라서 신기했고 메모리 사용량이 많다면 한 번 고려해보는것도 좋을것같다.

아니! 사실 BFS로 풀것이다 허허..

 

그래도 출력은 다 잘 나왔기에

재귀에 더 익숙해져봐야겠다.