1987번 - 알파벳
pop을 통해 set 내의 임의의 값을 제거/방문하더라도 정답을 풀 수 있고 오류 없습니다. 애초에 백트래킹을 복원할 필요가 없습니다. bfs, dfs, 다익스트라 등의 알고리즘은 기본적으로 XXX-first search라고 일반화하여 볼 수 있는데 pop을 쓰는 경우는 random-first search(임의의 용어)라고 볼 수 있고 이 경우도 아무런 문제 없습니다.
참고로 이런 문제가 아니라 일반적인 최단 경로 문제 역시 그러한 random-first search로도 풀 수 있습니다. 해본 적은 없고 아마 느리긴 하겠지만요.
채점 현황을 보니 작성자님의 코드는 pypy로 4500ms가 걸린 걸 확인할 수 있는데 set를 올바르게 쓰면 이보다 10배 가량 빠르게 풀 수 있습니다.
댓글을 작성하려면 로그인해야 합니다.
sky4soil 1년 전
하도 시초가 나서 list -> DAT -> set으로 자료 구조 혹은 참조를 좀 더 빠르게 할 수 있도록 최적화하던 도중 pop로 답을 작성할 경우 가장 최근 값을 제거한다는 보장이 없기때문에 운 좋게 백트랙킹 복원이 되는 경우와 그렇지 않은 경우로 나뉩니다. 그래서 remove로 정확히 지정해서 적어줘야 하는데, 누군가는 pop로도 정답을 맞힌 경우가 조금 있네요 오류 같습니다.