WHAT WE TAGS 너비우선탐색 LIST
실습과제 BFS 알고리즘 최단 경로용 bfs의 각 단계는 아래와 같다. 큐에 아무 Node도 없을 때까지: 큐에서 가장 앞 Node를 꺼낸다 이 Node에 인접해 있는 Node들을 돌면서: 처음 방문한 Node면: 방문한 Node로 표시한다 최단 경로용으로 쓸때는 이 부분이 새롭게 추가되는데, predecessor 변수를 설정한다 마지막에 Node를 큐에 넣는다
BFS 알고리즘을 이용한 predecessor 방식이 진짜 최단 경로가 맞는지 어떻게 확신할 수 있을까? 이번 장에서는 증명해보겠다. 이것을 이해하기 위해서는 BFS가 Node를 방문하는 순서를 살펴봐야 한다. BFS는 시작 Node 를 먼저 본다. 그리고 이 시작점에서 인접한 Node 들을 모두 방문한다. <img src="/media/post-body/2021/09/27/image_lf2Gceu.png" style="max-width:250px;
아래와 같은 빈 큐와 그래프가 있다고 가정하자. 여기에 BFS 알고리즘을 사용할 것이다. 각 Node 의 predecessor 는 보기 편하게 표로 나타내겠다. 먼저 시작점 Node를 방문했다고 표시한다. 시작점은 아무데서도 오지 않았다. 그러니 이전 Node가 없는 것이다. predecessor 는 없다고 표시한다. 시작점 Node A 를 큐에
BFS를 할 때는 각 Node 는 그 Node 를 방문한 적이 있는지 없는지 표시하는 목적으로 visited라는 변수를 저장한다. 사진에서는 이 visited 를 변수를 Node의 색으로 나타냈다. 최단 경로를 구할 때는 이 visited 변수에 추가로 predecessor 라는 변수도 저장해
BFS를 실행시키는 데 시간이 얼마나 걸리는지 알아보자. 총 Node 수를 V 엣지의 수를 E 라고 하자. BFS 알고리즘 (처음에 모든 노드를 방문하지 않았다고 표시) 시작점 노드를 방문한 노드 표시 후, 큐에 넣는다 큐에 아무 노드도 없을 때까지: 1. 큐에서 가장 앞 노드를 꺼낸다 2. 이 노드에
실습과제 그래프는 저번 챕터에서 만든 지하철 그래프를 그대로 사용할 것이다. 챕터 1에서는 수도권 지역 지하철 노선들만 사용했는데, 이번에는 대전 지하철 노선도 추가하겠다. BFS 알고리즘 좀 더 편하게 구현하실 수 있게 BFS 알고리즘을 일반화한 걸 여기 붙여 넣겠다. 시작점 노드를 방문한 노드 표시 후, 큐에 넣는다 큐에
이런 그래프와 빈 큐가 있다고 가정하자. BFS 는 시작점 Node 하나를 갖는다. 여기서는 A 라고 가정하자. 알고리즘을 진행하면서 이미 방문한 Node들과 그렇지 않은 Node들을 구별해 줘야된다. 애니메이션에서는 찾은 Node들을 색으로 구별할 것이다. 방문하지 않은 Node 색은 살색, 방문한 Node는 회색으로 표현하곘다. <img
BFS 알고리즘에 대해서 본격적으로 시작하기 전에 미리 알아야 할 추상 자료형이 있다. 큐 복습할 추상 자료형은 바로 큐이다. 기본 자료형 토픽에서 조금 더 구체적인 설명이 있긴 하니까 여기서는 좀 더 간략하게 알아볼 것이다. 큐는 맨 뒤에 데이터 삽입 맨 앞 데이터 삭제 맨 앞 데이터
BFS의 Breadth 는 영어로 너비를 뜻한다. 아래와 같은 사각형이 있으면 이 사각형의 가로, 이걸 너비라고 한다. 쉽게 생각해서 높이 혹은 깊이와 반대되는 표현이라고 생각하면 된다. 그래서 BFS는 너비를 우선 탐색하겠다는 말이다. 그래프에서 너비를