다익스트라 (1) 썸네일형 리스트형 [백준 9376][C++] 탈옥 문제 https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 풀이 과정 [참고 링크 1] [참고 링크 2] [0-1 BFS 알고리즘 링크] 필자는 링크 1의 코드를 기반으로 풀이를 작성했다. 해당 문제는 0-1 BFS 알고리즘을 통해 다익스트라 알고리즘보다 효율적으로 구현할 수 있다. 주변의 위치에 존재하는 BFS탐색 시, 문이거나 문이 아닌 경우로 나뉘기 때문이다. 이 문제의 핵심은 아래 3가지 경우를 모두 고려해야 한다는 점이다. 1) 1번 죄수가 탈출하며 문.. 이전 1 다음
