목록알고리즘/이론 (1)

개발세발은 안되요

[C++] 0-1 BFS

BFSBFS는 거리(또는 시간 등)이 짧은 것부터 차례로 계산함.BFS로 어떤 지점에 '처음 도달'했을 때가 항상 최단 시간(=거리) 이다.예를 들어, n이라는 위치에서 출발해서 1초 뒤에 갈 수 있는 곳, 2초 뒤에 갈 수 있는 곳~ 이런 식으로 넓혀가는 것임. 0-1 BFS 일반적인 BFS와는 다르게 경로에 따라 가중치가 달라지는 경우에 해당한다. 즉 이동할 때 비용이 0이거나 1밖에 없는 경우에 사용하는 특수한 BFS이다. 이 경우 일반적인 BFS로는 풀기 어려울 수 있다.일반 BFS는 큐에 넣는 순서대로 탐색함.즉 비용에 따른 우선순위를 고려하지 못함. 따라서 일반적으로 BFS에서는 queue를 이용해 구현하지만, 0-1 BFS는 deque를 이용하여 덱의 앞(front)와 뒤(back)에 각..
알고리즘/이론 2025. 4. 28. 21:17
이전 Prev 1 Next 다음