DFS Python (1) 썸네일형 리스트형 [Python] 백준 1987번 문제, 알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 이 문제는 백트래킹을 사용해서 시간을 단축해야 하는 문제이다. 기존 DFS를 수행한다면, 매 경우를 탐색해야 하기 때문에 비효율적이다. 그래서 일정 조건에 부합할 경우 그 위치 p를 저장해 한 턴이 끝났을 때 처음부터 시작하는 것이 아닌 저장해둔 그 위치 p부터 시작한다. 예시를 하나 들기 위해 구조가 (1) -> (2) -> (3)처럼 되어 있고 노드가 가진 자식 노드를 dic으로 표현하.. 이전 1 다음