[백준/파이썬] 1987번

📍백준 1987번 문제

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

코드

import sys
sys.setrecursionlimit(10**4)

input = sys.stdin.readline
ans = 0

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
n, m = map(int, input().split())
graph = []
for _ in range(n):
    graph.append(list(input()))
visitedSet = set()


def dfs(x, y, cnt):
    global ans
    ans = max(ans, cnt)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if ((0 <= nx < n) and (0 <= ny < m) and not graph[nx][ny] in visitedSet):
            visitedSet.add(graph[nx][ny])
            dfs(nx, ny, cnt + 1)
            visitedSet.remove(graph[nx][ny])


visitedSet.add(graph[0][0])
dfs(0, 0, 1)
print(ans)

풀이

경로에 대한 최댓값을 구하는 것이므로 DFS로 구현해야 한다.

하 계속 메모리 초과 / 시간 초과 떠서 너무 빡쳤는데..^^...
python 대신 pypy3
import sys
sys.setrecursionlimit(10**4)를 위에 적는다면 맞다곤 뜬다 ㅎㅎ...