1002ever   10달 전

1987번 파이썬 구현 시간 초과... 어디가 문제일까요?

trace_alpha 에 경로 저장

visited 배열 활용한 4방향 탐색 dfs 코드로 구현하였습니다.

길이 막히면(bp == 0)

경로 길이와 max를 대조하여 변경해줬습니다..

pypy3 로도 돌아가질 않네요ㅠㅠ

어떻게 줄일 수 있을까요?

wider93   10달 전

list의 원소인지를 확인하는 것은 느립니다. trace_alpha를 set으로 바꾸면 조금 더 빨라지겠네요.

문제라면 조금 더 빨라지는 정도로는 통과할 수 없어 보입니다.

경로의 길이에 따라 탐색해야 하는 양이 지수적으로 높아지기 때문에, 모든 경로를 따로 탐색해서는 통과하기 어렵습니다.

좌표마다 도착했을 때 가능한 알파벳 조합을 다 모아두는 등 좀더 처리가 필요합니다.

댓글을 작성하려면 로그인해야 합니다.