BOJ 1926 : 그림 (Python)

문제

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

1926번: 그림

 

 

코드

import sys
sys.setrecursionlimit(10**7)

def dfs(x,y):
    global temp
    if x<=-1 or x>=n or y<=-1 or y>=m:
        return False
    if graph[x][y] == 1:
        graph[x][y] = 0
        dfs(x-1,y)
        dfs(x,y-1)
        dfs(x+1,y)
        dfs(x,y+1)
        temp += 1
        return True
    return False

n,m = map(int, input().split())

graph = []
for i in range(n):
    graph.append(list(map(int, input().split())))

result = 0    
maximum = 0
for i in range(n):
    for j in range(m):
        temp = 0
        if dfs(i, j) == True:
            result += 1
            if maximum < temp:
                maximum = temp
print(result)
print(maximum)

 

 

풀이

 

이코테 강의에서 나온 문제와 유사해서 그 코드에서 좀만 더 추가해서 문제를 풀었다... 다시 기억해내서 혼자해보려니까 기억이 안나더라.. 복습해야하는데...

 

1이 붙어있는 것들이 그림에 해당한다. 그러므로 한 원소를 기점으로 상하좌우에 1이 있으면 그림으로 취급하면 된다. 이렇게 DFS를 이용해서 모든 원소를 확인해본다.

 

dfs 메소드가 True를 리턴하면(graph[i][j]를 기준으로 주변의 그림 여부 탐색이 끝나면) result 라는 변수에는 1을 더해서 그림의 총 개수를 측정한다.

그리고 dfs 탐색이 한번 끝날 때마다 temp 라는 변수에 1을 더해서 그림의 크기를 측정한다.

maximum 변수가 temp보다 작으면 maximum에 temp 값을 대입해서 가장 큰 그림의 크기를 저장할 수 있도록 한다. 

 

처음에 백준에서 Recursive error가 났었는데 파이썬의 재귀 한도를 넘어서서 생긴 오류라고 한다. 구글링을 해보니

sys.setrecursionlimit(10**7)

위와 같이 재귀 한도를 늘려주면 된다고 한다. 뭔가 억지로 코드가 돌아가도록 만든 느낌이나 ... 다른 방법은 생각이 안난다.