2년 전에 유기했던 DFS를 풀어.. (#1987)

#1987 알파벳 (https://www.acmicpc.net/problem/1987)

 

과거 소마를 준비하던 시절 포기했던 문제였다.

 

 

 

 

틀린 코드

r, c = map(int, input().split())

graph = [[x for x in input()] for _ in range(r)]

alpha = set(graph[0][0])
dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]
answer = 0


def solve(x,y, length):
    global answer
    answer = max(answer, length)

    for i in range(4):
        nr = x + dr[i]
        nc = y + dc[i]
        if 0 <= nr < r and 0 <= nc < c and not graph[nr][nc] in alpha:
            alpha.add(graph[nr][nc])
            solve(nr, nc, length+1)
            alpha.remove(graph[nr][nc])


solve(0, 0, 1)

print(answer)

 

무엇이 문제였을까??

 

아무리 생각해도, set을 사용하는 과정에서 remove, in 등을 사용했기 때문으로 보인다. ( O(n) )

 

문뜩, 그런 생각이 들었다.

왜 알파벳으로 맵을 만들었을까?

 

알파벳은 순서가 있어, index로 응용할 수 있다.

 

아.. 이거구나..

 

정답코드

import sys
input = sys.stdin.readline

r, c = map(int, input().split())

graph = [[x for x in input()] for _ in range(r)]


alpha = [0] *26
alpha[ord(graph[0][0]) - ord("A")] = 1
dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]
answer = 0


def solve(x,y, length):
    global answer
    answer = max(answer, length)

    for i in range(4):
        nr = x + dr[i]
        nc = y + dc[i]
        if 0 <= nr < r and 0 <= nc < c :
            idx = ord(graph[nr][nc]) - ord("A")
            if alpha[idx] == 0:
                alpha[idx] = 1
                solve(nr, nc, length+1)
                alpha[idx] = 0

solve(0, 0, 1)

print(answer)

 

알파벳을 인덱스로 사용했더니, 시간초과를 면할 수 있었다.

 

문제에 데이터가 알파벳으로 주어진다면, 고정된 리스트를 만들고 알파벳을 인덱스로 활용해야겠다는 아이디어로 연결될 필요가 있지 않을까?