[BOJ] 1987. 알파벳

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

1987번: 알파벳

 

 

1. 해결방법

상하좌우를 이동하면서 배열에 넣고 방문 여부 체크를 하도록 했다.
방문 체크를 하기 때문에 중복으로 들어가는 알파벳이 없고, DFS 재귀를 이용해서 계속적으로 그래프를 탐색할 수 있다.

위를 인지하고 완전 탐색을 이용하여 해결하였는데,,, 시간초과가 떠버렸다....
아마 이유는 리스트에서 append와 pop을 사용한 문제인 것 같았다. 물론 set()를 이용한 add, remove도 사용하였지만 마찬가지로 시간초과가 나와버렸다... 미친;;

list에서 append와 pop이 생각 이상으로 시간복잡도를 잡아먹기 때문에, 다른 방법을 생각해 보았다.

알파벳을 ord() 메서드를 이용해서 아스키 코드로 변환해주고 알파벳 전부를 방문 여부 체크를 하면 된다.
물론 python3로는 통과를 못했지만 pypy3로는 통과를 했다,,,

 

 

1-1 시간초과 코드

import sys
input = sys.stdin.readline
from itertools import permutations, combinations


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


# dfs
def dfs(y, x, count):
    global answer

    answer = max(answer, count)

    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]
        if 0 <= ny < R and 0 <= nx < C:
            if maps[ny][nx] not in verify_alpha:
                verify_alpha.append(maps[ny][nx])
                dfs(ny, nx, count + 1)
                verify_alpha.pop()


# main
verify_alpha = []
dy, dx = [0, -1, 0, 1], [1, 0, -1, 0]
verify_alpha.append(maps[0][0])
answer = 1
dfs(0, 0, 1)
print(answer)

 

 

2. 정답코드 (pypy3)

import sys
input = sys.stdin.readline
from itertools import permutations, combinations


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


# dfs
def dfs(y, x, count):
    global answer, chk

    answer = max(answer, count)

    for i in range(4):
        ny, nx = y + dy[i], x + dx[i]
        if 0 <= ny < R and 0 <= nx < C:
            if chk[ord(maps[ny][nx]) - 65] == False:
                chk[ord(maps[ny][nx]) - 65] = True
                dfs(ny, nx, count + 1)
                chk[ord(maps[ny][nx]) - 65] = False


# main
dy, dx = [0, -1, 0, 1], [1, 0, -1, 0]
chk = [False] * 26
chk[ord(maps[0][0]) - 65] = True
answer = 1
dfs(0, 0, 1)
print(answer)