[Python] 백준 1987: 알파벳 (탄압받는 파이썬, 극한의 소요 시간 줄이기)

🔗 문제 링크

1987번: 알파벳

💊 문제 요약

세로 R칸, 가로 C칸인 표 모양의 보드판이 있다. 각 칸에는 알파벳 대문자가 적혀있고, 1행 1열에 말이 놓여있다.
말은 상하좌우 1칸씩 이동이 가능하며, 지금까지 지나오지 않은 알파벳이 적힌 칸으로만 이동할 수 있다.
좌측 상단으로부터 말이 최대 몇 칸 움직일 수 있는지 구하시오. 단, 좌측 상단의 카드도 포함된다.

🌿 풀이 설명

 

나의 멘탈을 다소 흔들었던 알파벳 문제... 🥹

 

문제 해결을 위한 의식의 흐름은 이러했다.

BFS가 익숙했어서 deque를 사용하여 문제를 해결해보려 한다. → deque에 append하는 형식은 (current_x, current_y, distance, passed_alphbets (set))로 하고, visited도 넣고... → 시간 초과

 

BFS를 왜 쓰는가, DFS를 왜 쓰는가 각 알고리즘의 목적을 다시 되짚어본다.

BFS를 사용했던 유형에는 어떤 말을 이동하는 거리를 구할 때 장애물이 있어 상하좌우를 탐색한 뒤, 이동이 가능한지 분별하는 경우가 있었다. 이런 경우는 DFS를 써도 무관한데...

 

그럼 visited와 같은 [위치, 이동 거리]를 제외한 정보값을 고려해보자. 필요한 정보는 지금까지 지나온 알파벳들, 이들은 다음 경로의 알파벳이 지금까지 지나온 알파벳에 있는지 확인하기 위해 필요하다. element in iterable의 시간 복잡도가 set은 O(1), list는 O(N)이므로 set을 사용한다. 

※ 지나온 알파벳 경로를 string으로 저장하여 해결한 경우가 있었다. (string 풀이 바로가기)

string은 다음 BFS, 또는 DFS로 넘길 때 copy() 연산이 필요없어서 set만큼 적은 시간이 가능하지 않았나 싶은데, 실제로 초기 시도에서 set을 사용하고도 시간 초과가 났어서 set보다 더 적은 시간이 걸리는 것으로 보인다.

 

이 과정에서, 질문 게시판을 참고하였고 DFS를 사용하여 나온 코드는 아래와 같다.

코드 보기

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

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

def dfs(x, y, dist, alpha_set):
    global max_dist
    max_dist=max(dist, max_dist)
    for i in range(4):
        cx=x+dx[i]
        cy=y+dy[i]

        if 0<=cx<R and 0<=cy<C:
            if board[cx][cy] not in alpha_set:
                alpha_set.add(board[cx][cy])
                dfs(cx, cy, dist+1, alpha_set.copy())
                alpha_set.remove(board[cx][cy])
                continue

dfs(0,0,1,set(board[0][0]))
print(max_dist)

※ 수정: 위 오답 코드에서 set을 copy()하는 것은 의미가 없다.! copy()를 쓰지 않고 다시 제출해봤는 시간 초과가 났다 🥲 코딩 테스트 고수님의 의견에 따르면, set이 상대적으로 느린 자료 구조라는데 정확한 내용은 조금 더 의견을 여쭙는 것으로...

 

하지만 여전히 시간 초과 😭

시름에 잠겨버린 난 고민 후, 정답 코드 포스팅을 보게 된다.

[Python] 백준 1987번 : 알파벳

 

이 풀이의 핵심은 set.copy()를 만들지 않는 것이다.

길이가 26인 boolean list와 DFS, ord()를 활용하여 이를 가능하게 하였다.

 

정답 코드

import sys
input=sys.stdin.readline
R, C=map(int, input().rstrip().split())
board=[[ord(x)-65 for x in input().rstrip()] for _ in range(R)]

max_dist=0
dx=[1, -1, 0, 0]
dy=[0, 0, 1, -1]
alpha=[False for _ in range(26)]
alpha[board[0][0]]=True

def dfs(x, y, dist):
    global max_dist
    max_dist=max(dist, max_dist)
    for i in range(4):
        cx=x+dx[i]
        cy=y+dy[i]

        if 0<=cx<R and 0<=cy<C:
            if not alpha[board[cx][cy]]:
                alpha[board[cx][cy]]=True
                dfs(cx, cy, dist+1)
                alpha[board[cx][cy]]=False
                continue

dfs(0,0,1)
print(max_dist)

알파벳 갯수가 26개이므로, 이를 활용하면 좋겠다고 막연히 생각했는데, ord로 각 알파벳을 index로 전환한 점이 참신하게 느껴졌다.

이렇게 하고도, PyPy를 사용하여야 통과되었다. 🥹

여러 가지 문제를 풀며, 유용한 파이썬 라이브러리가 많다는 것을 실감한다.
이번 문제에서는 ord와 chr 함수가 그러했다!