목록2023/01/19 (1)

코딩관계론

[카카오 2023 블라인드] 미로탈출명령어

독자는 BFS, DFS 알고리즘을 이해하고 있어야 하고, 해당 문제를 한번이라도 읽었어야 함 아이디어 도출 방법 문제의 조건을 체크해보면 아래의 조건이 존재합니다. 미로에서 탈출한 경로를 문자열로 나타냈을 때, 문자열이 사전 순으로 가장 빠른 경로로 탈출해야 합니다. 같은 격자를 두 번 이상 방문해도 됩니다. 격자의 범위를 나갈 순 없다. 우선 1번 조건을 수행하기 위해서 우선순위 힙을 이용해 방문 순서를 정렬했고, 항상 사전순으로 빠른 후보지를 선택할 수 있었다. 같은 격자를 두 번이상 방문하는 것을 해결하는게 이 문제의 포인트였다. 같은 격자를 두 번 방문하게 되면 또 다시 4개의 선택지가 큐에 들어가기 때문에 탐색량이 많아지게 된다. 이런 문제를 해결하기 위해 가자치기를 수행했다. 총 두 가지 가지..
개발/알고리즘 2023. 1. 19. 14:36
이전 Prev 1 Next 다음