Algorithem/백준 PS with code
백준 #1987 - [G4] 알파벳 : 백트래킹, 시간초과
(python3) 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 백트래킹 전형적인 dfs 백트래킹으로 해결할 수 있습니다. 매번 4방향으로 재귀를 돌고, 들렀던 알파벳을 만나면 끝내는 방식으로 적용합니다. 시간초과 이미 들렀던 알파벳을 어떻게 확인할것인가? 부분에서 어떤 방식과 자료구조를 취하느냐에 따라 시간초과가 발생할 수 있습니다. 저는 3가지 방식을 적용해봤습니다. 1. deque : 들렀던 알파벳을 deque 에 append 하고, 백트래킹에서 빠져나올때 pop 하는 형식. in 으로 들렀..
