[BOJ/백준] 1987 알파벳

# 1987 알파벳

def dfs(x,y,visited,cnt):
    global result,const,ccs
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx< R and 0<= ny<C and visited[ord(arr[nx][ny])-const]:
            visited[ord(arr[nx][ny])-const] = False
            dfs(nx,ny,visited,cnt+1)
            visited[ord(arr[nx][ny])-const] = True
    if cnt > result:
        result = cnt
ccs = 0
R,C = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(input()) for _ in range(R)]
result = 1
visit = [True]*26
const = ord('A')
visit[ord(arr[0][0])-const] = False
dfs(0,0,visit,1)

print(result)

시간 초과의 늪에 빠졌던 문제이다. 기본적인 원리는 찾았으나, 문제를 해결하기 위한 방안을 찾기위해 노력했던 문제이다.

처음으로 풀었던 방식은 원래는 visited를 하나의 집합으로 해서 있는지 없는지 체크를 했다면, 알파벳에 해당되는 visited 리스트를 만들어주고 check 해주는 방식으로 풀었다.

 

 

# 1987 알파벳


R,C = map(int,input().split())

arr = [list(input()) for _ in range(R)]
check = [['']*C for _ in range(R)]

stack = [(0,0,1,arr[0][0])]
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
while stack:
    x,y,cnt,total = stack.pop()
    if result < cnt:
        result = cnt
    if result == 26:
        break
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < R and 0<= ny <C:
            if arr[nx][ny] not in total:
                temp = total + arr[nx][ny]
                if check[nx][ny] != temp:
                    check[nx][ny] = temp
                    stack.append((nx,ny,cnt+1,temp))
print(result)

시간이 빠른 방식은 다음과 같다. visited를 체크하는 것은 하나의 스트링을 통해 그 안에 있는지 없는지 확인하는 것이다.

여기까지는 동일하다. 하지만 결정적으로 다른것은 check라는 행렬을 통해 또 체크 하는 것이다.

지금까지 온 이동경로를 넣어놓는 check라는 행렬이다. 이 행렬에 존재하는 값과 같으면, 이미 그에 대해서 전부 탐색을 한 것이기 때문에 또 다시 탐색할 필요가 없다.

 

탐색한 경로들을 캐싱해놓은것과 같다. 서로다른 루트로 왔다 하더라도 다음위치에 똑같은 값으로 들어오는 거면 굳이 한번 더 검색을 할 필요가 없다.

 

이 방법은 dfs나 bfs 상관은 없으나 bfs를 할 시, collections의 deque를 쓰도록 하자. 안 그러면 시간 초과가 난다.