[파이썬, Python] 백준 1987: 알파벳

문제

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

1987번: 알파벳

코드

r, c = map(int, input().split())
board = [list(input()) for i in range(r)]
visited = set()
ans = 0

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def dfs(x, y):
    global ans
    visited.add(board[x][y])
    ans = max(ans, len(visited))

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
    
        if 0 <= nx < r and 0 <= ny < c and board[nx][ny] not in visited:
            dfs(nx, ny)
            visited.remove(board[nx][ny])
            
dfs(0, 0)

print(ans)

설명

결론부터 말하면 PyPy3로 해결했다.
Python 3로는 어떻게 해도 시간 초과의 늪에서 벗어날 수 없었다.

기존에 리스트로 visited를 처리해서 방문한 알파벳을 넣는 방법을 사용했는데
이는 시간적인 부분에서 손해가 있어서
set으로 변경해 주고 add와 remove 하는 방법으로 시간을 줄였다.

사실 리스트로도 가능할 것 같은데 잘 모르겠다.

우선 dfs의 진행 자체는 일반적인 dfs 문제와 크게 차이가 없었다.
조금의 차이점이라면 global을 사용해서 전역 변수에 있는 ans와 현재 visited의 개수를 비교하는 점 정도가 있겠다.

그 외에는 기본적인 백트래킹을 사용해서 방문한 알파벳에 대해서는 방문하지 않는 방법을 이용했다.
처음에 방문한 알파벳에 대해서 방문 처리를 해주고(visited에 넣어주고)
나중에 빠져 나올 때 제거를 해주었다.