[BOJ] 알파벳

---

코드

from sys import stdin
input = stdin.readline

def dfs(x, y, t, visitedApb):
    global ans
    # print(x, y, t, visitedApb)
    for d in [(-1,0), (1,0), (0,-1), (0,1)]:
        nx, ny = x + d[0], y + d[1]
        if 0 <= nx < R and 0 <= ny < C:
            if not visitedApb[ord(bd[nx][ny])-65]:
                visitedApb[ord(bd[nx][ny])-65] = 1
                dfs(nx, ny, t+1, visitedApb)
                
    # 횟수 갱신
    if t > ans:
        ans = t
    # 함수 스택에서 빠져나가기 전에 방문한 알파벳 미방문 처리
    visitedApb[ord(bd[x][y])-65] = 0
    return t

# input
R, C = map(int, input().split())
bd = []
for _ in range(R):
    bd.append(list(input().rstrip()))

ans = 0
visitedApb = [0]*26
visitedApb[ord(bd[0][0])-65] = 1
dfs(0,0,1, visitedApb)
print(ans)

결과

풀이 방법

• DFS를 활용해야 하는 문제이다.
• 재귀를 사용하여 DFS를 구현하였으며, 인접한 좌표 중 현재까지 나오지 않은 알파벳인 경우에만 방문한다.
• 현재까지 나온 알파벳을 list에 추가하여 관리하고 if not in 문으로 체크하면 시간초과가 발생하였다.
• 따라서 알파벳의 index에 방문여부를 0, 1로 관리하여, 체크 과정의 시간복잡도를 O(1)로 만들었더니 통과하였다.
• 또한 재귀함수를 함수 스택의 top에서 제거하기 전에 방문한 알파벳을 다시 미방문 처리하여야 이전의 위치에서 다른 인접한 좌표를 방문할 수 있다. 해당 좌표를 시작으로 DFS를 수행했을 때 더 깊이 방문할 가능성이 있기 때문이다.

---