0-1 BFS2 [알고리즘] 0-1 BFS edge가 0 혹은 1의 가중치를 가질 때 사용하는 bfs이다. 사용하는 자료 구조 - 덱 접근 - 다익스트라 알고리즘을 최적화시킨 것이다. 사실 다익스트라 써도 상관없다. 다익스트라도 가중치 있는 노드에서 최단 거리 찾는 알고리즘이기 때문. - 가중치가 0이라는 것은 이전 노드와 동일 레벨이 존재한다는 것이다. 가중치가 1이면 이전노드에 비해 한 레벨 아래에 존재한다는 의미. - 가중치가 0인 것을 우선으로 팝하기 위해 가중치가 0인 경우 큐 앞쪽에, 가중치가 1인 경우 큐 뒤쪽에 푸쉬한다. 하지만 일반적인 큐는 앞에 푸쉬하는 것이 불가능하기 때문에 덱을 사용해서 앞쪽에 푸쉬한다. #include int main(void){ deque dq; dq.push_front(시작노드); while(!dq.em.. 2020. 10. 29. [백준 13549] 숨바꼭질3 www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 단순 bfs로 접근했다가 틀렸다. 단순 bfs로 접근하면 안되는 이유는 순간이동시에 2*x를 이동하지만 0초가 걸리기 때문이다. 현재 노드에서 아래 레벨로 접근하는게 아니라 같은 레벨 상에 노드가 하나 더 생기는 셈이다. 사용하는 알고리즘 0-1 bfs 0-1 bfs란 그래프에 가중치가 0과 1로 구성된 경우 사용하는 bfs이다. 여기서 가중치란 노드의 레벨로 보면 될 것 같다.. 2020. 10. 29. 이전 1 다음