Algorithm/acmicpc.net
2년 전에 유기했던 DFS를 풀어.. (#1987)
winney916
2024. 9. 20. 11:17
728x90
#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)
알파벳을 인덱스로 사용했더니, 시간초과를 면할 수 있었다.
문제에 데이터가 알파벳으로 주어진다면, 고정된 리스트를 만들고 알파벳을 인덱스로 활용해야겠다는 아이디어로 연결될 필요가 있지 않을까?