boj.kr/1987 알파벳 (gold4) 파이썬 풀이

1. 방문한 좌표의 알파벳을 중복 제거해 저장할 set 자료형 변수 초기화

2. 그래프 순회하면서 방문하지 않은 알파벳이면 set 자료형 변수에 저장하고 dfs 후 삭제

3. 매 dfs 마다 최대 거리수를 저장

4. 최대 거리수 출력

 

R, C = map(int, input().split())
graph = [list(input().strip()) for _ in range(R)]

visited = set(graph[0][0])
max_d = 1

dy = (-1, 1, 0, 0)
dx = (0, 0, -1, 1)
def dfs(y, x, d):
    global max_d
    max_d = max(max_d, d)

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0<=ny<R and 0<=nx<C:
            if graph[ny][nx] not in visited:
                visited.add(graph[ny][nx])
                dfs(ny, nx, d+1)
                visited.remove(graph[ny][nx])

dfs(0, 0, max_d)
print(max_d)

 

sys.setrecursionlimit(10**6) 을 추가하면 PyPy3으로 제출해도 메모리가 초과가 발생한다.

dy 를 (-1, 1, 0, 0) 으로 주고 dx 를 (0, 0, -1, 1) 으로 주지 않으면 시간 초과가 발생한다.