[백준] 1987: 알파벳 python 구현 / DFS, 시간초과(pypy3, python3)

글을 쓰기에 앞서,, pypy3으로 돌리면 해결될 문제를 1시간 동안 붙잡았던 건에 대하여,,,

Python3 vs PyPy3

• python3 : 메모리 및 속도 측에서 우세
• pypy3: 복잡한 코드(반복)을 사용하는 경우 우세

---

PyPy3에서 사용하는 JIT(just in time) 컴파일이란 프로그램을 실행하기 전에 컴파일 하는 대신, 프로그램을 실행하는 시점에서 필요한 부분들을 즉석으로 컴파일 하는 방식이고 보통 인터프리터 언어의 성능 향상을 목적으로 도입하는 경우가 많다. 인터프리트 하면서 자주 쓰이는 코드를 캐싱하기 때문에 인터 프리터의 느린 실행속도를 개선할 수 있다. JVM에서도 바이트 코드를 기계어로 번역할 때 JIT 컴파일러를 사용한다고...

 

Link에서 이해할 수 있었습니다,, 더 자세한 내용은 해당 블로그를 방문하시는 것을 추천 !

아무튼 중요한건 코드 상황에 맞추어 두 구현체를 적절하게 사용하는 것 !

 

문제

세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

 

풀이

DFS로 구현하였다.

python3로는 시간 초과가 나는 것을 모르고 조건을 추가하고자 이것 저것 노력을 하긴 했다.

일단 처음에는 같은 알파벳이 적힌 칸을 두 번 지날 수 없다는 조건 때문에 python의 not in 조건을 사용하고자 했다. 그러나 이렇게 사용하면 시간 복잡도가 계속 증가하기 때문에 dictionary를 사용해야 한다는 것을 깨닳았다.

하여 사용한 방법은 아래처럼 문자열 dict를 만들어 주는 방식이다.

alpha_dict = {ord(i):0 for m in Map for i in m}

이후에도 계속 시간초과가 나서 .. 코드를 찾아보다가 dictionary는 O(1)이거나 운이 좋지 않으면 O(n)이라서 리스트 인덱싱을 사용해야 한다는 글을 보고서는

ord('문자열')을 통해 문자를 아스키코드로 바꾸고 vst = [0]*26을 통해 방문처리를 하는 방법으로 바꾸었다.

 

뭐 결국은 둘 다 맞았다.

 

처음 본인이 작성한 코드를 첨부한다.

 

CODE

import sys

r, c = map(int, input().split()) # R: 세로, C: 가로
Map = []
for _ in range(r):
    Map.append(list(sys.stdin.readline().strip()))

max_cnt = 1
alpha_dict = {ord(i):0 for m in Map for i in m} 
def dfs(x, y, cnt):
    # 방향 정의
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]

    global max_cnt
    if max_cnt < cnt :
        max_cnt = cnt

    if len(alpha_dict) == max_cnt:
        return

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx<0 or ny<0 or nx>(r-1) or ny>(c-1): continue

        if not alpha_dict[ord(Map[nx][ny])]: ## 등장 횟수가 0
            alpha_dict[ord(Map[nx][ny])] = 1
            dfs(nx, ny, cnt+1)
            alpha_dict[ord(Map[nx][ny])] = 0


alpha_dict[ord(Map[0][0])] += 1
dfs(0, 0, max_cnt)
print(max_cnt)

+) 근데 같은 dictionary를 통한 접근인데 alpha_dict['A']  보다는 alpha_dict[ord('A')]의 접근이 훨씬 빠른가보다... ord() 안쓰면 같은 코드인데 시간 초과 남