[백준] 1926 파이썬(python) : 그림 - (DFS 메모리초과(방향벡터x))

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

1926번: 그림

 

 

 

DFS로 제출하면 메모리초과가 발생하는 문제다. 너무 자주 틀려서 블로그의 다른 코드를 읽지도 않고 이것도 틀릴까?해서 넣었는데 그것들도 틀렸다. 단념하고 BFS로 바꿀까 하다가 DFS로 풀어도 통과하는 코드를 찾을 수 있어서 그 분의 코드를 참고했다.

 

방향벡터와 방문처리 리스트 visit을 삭제해줘야 메모리초과가 발생하지 않는다.

 

import sys
from collections import deque
sys.setrecursionlimit(10**6)
n, m = map(int, sys.stdin.readline().split())
graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]
cnt, max_cnt = 0, 0

res = []
def dfs(x, y):
    global cnt
    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False
    if graph[x][y] == 1:
        cnt += 1
        graph[x][y] = 2 # 방문처리
        dfs(x+1, y)
        dfs(x-1, y)
        dfs(x, y-1)
        dfs(x, y+1)
        return True
    return False
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            cnt = 0
            dfs(i, j)
            res.append(cnt)
print(len(res))
if len(res) == 0:
    print(0)
else:
    print(max(res))

 

다른 DFS문제와 차이가 없는 로직이라서 따로 주석을 달지는 않겠다. 다음부터는 DFS로 풀다가 메모리 초과가 나오면 그냥 단념하고 BFS로 바꿔서 풀어야겠다. 재귀함수 연습한다고 DFS를 고집했지만 기력만 빨아들이고 남는게 없는것 같다.