6.너비우선탐색(BFS) / 깊이우선탐색(DFS)

 

두가지 방식 모두 그래프를 이용하여 표현

 

 

 

 

깊이우선탐색

 

 

1. 깊이우선탐색(DFS : depth first search)

 

-하나씩 자식노드들을 끝까지 파고 내려간다

 

-재귀함수로 구현하면 더 간단해진다

 

-스택사용

 

 

 

 

 

 

 

 

 

너비우선탐색

 

2. 너비우선탐색(BFS : Breadth first search)

 

-노드들을 단계별로 나누어 한단계씩 탐색해나간다

 

-같은 레벨에 있는 노드들끼리 탐색한다

 

(루트 - 첫번째 자식 노드들 - 두번째자식 노드들 - 세번째자식 노드들)

 

-큐사용

 

 

 

 

 

 

 

 

 

 

 

-너비우선탐색을 이용하면 최단 경로를 찾을 수 있다

 

최단 경로는 여러 의미로 사용될 수 있다

 

ex)

 

1: 체스 게임에서 가장 적은 수로 승리하는 방법 (최소한의 수)

 

2.맞춤법 검사기(가장 적은 개수의 글자를 고쳐서 올바른 단어를 만드는 방법찾기)

 

3.현재 네트워크에서 가장 가까운 의사찾기

 

 

 

 

 

 

<출발지에서 금문교까지의 최단 경로찾기>

 

<트윈픽스 -> 금문교> 최단 경로 찾기(너비 우선탐색)

 

 

 

출발지에서 1단계만에 갈 수있는 노드들 확인 -> 금문교 도착확인 (yes or no)

 

-> (no) 2단계만에 갈 수있는 노드들 확인 -> 금문교 도착확인 (yes or no)

 

-> (no) 3단계만에 갈 수있는 노드들 확인 -> 금문교 도착확인 (yes or no)

 

-> (yes : 금문교 도착) 금문교 도착까지의 최단거리는 3단계

 

 

출발지에서 금문교까지 가는데에는 최소한으로 가면 3단계가 걸린다

 

 

 

 

위와같이 그래프로 모형화 한뒤에 너비우선탐색으로 해결할 수 있다

 

 

 

 

 

 

 

너비우선탐색으로 

 

1. 경로가 존재하는가?

 

2. 최단경로는 무엇인가?

 

를 알 수 있다

 

 

 

 

 

 

<망고 판매상 찾기>

 

나의 친구가 3명일때 한명씩 망고 판매상인지 확인한다. 맞으면 바로 종료 아니면 다른 사람확인 반복

 

나의 친구(1단계 친구) : (프로도, 네오, 튜브)

 

망고 판매상이 아니라면, 그 사람의 친구들도 탐색목록에 추가한다.

 

(1단계 친구에서)망고 판매상이 없을 시 친구의 친구까지 확인한다

 

친구의 친구(2단계친구) : (라이언, 무지,제이지, 콘)

 

반복시 친구의 친구들까지 전체 그래프를 탐색하게 된다.

 

 

 

이러한 방식으로 너비우선탐색은

 

1.경로가 존재하는지(나의 네트워크에 망고 판매상이 존재하는지)

 

2. 최단경로가 무엇인지(누가 가장 가까운 망고판매상인지)

 

를 알 수 있게 해준다.

 

 

 

1단계 친구들을 먼저 확인해보고 없는 경우에만, 2단계 친구들을 확인한다.

 

그렇기에 너비 우선탐색이 진행될수록 탐색범위는 출발점에서 멀어진다

 

1단계친구들 확인 - 2단계친구들 확인 - 3단계친구들 확인

 

이렇게 순서대로 찾기때문에 자료구조 큐(선입선출)를 사용한다

 

 

 

 

 

<망고판매상 찾기 알고리즘>

 

1. 확인할 사람의 명단을 넣을 큐를 준비한다(프로도, 네오, 튜브)

 

2. 큐에서 한 사람을 꺼낸다

 

3.이 사람이 망고 판매상인지 확인한다(yes or no)

 

(yes) : 끝

 

(no) : 그 사람의 이웃을 모두 큐에 추가한다.

 

4.반복문 수행

 

5. 큐가 비어있다면 네트워크에 망고판매상이 존재하지 않는다

 

 

 

 

알고리즘이 종료되는 2가지 경우

 

1.망고판매상을 발견한 경우

 

2.큐가 비게되는 경우 (망고판매상이 존재하지 않는경우)

 

 

 

*조심해야할 부분

 

무지가 2명이서 함께 알고있는 친구인 경우, 무지가 망고 판매상인지 한번만 확인하면 된다.

 

그렇기 때문에 한번 확인한 사람은 다시 탐색되지 않도록 설정해야한다. 

 

그렇지 않으면 무한루프에 빠질 수 있다

 

(나 - 무지 - 나 - 무지)

 

 

 

 

코드 구현) 

 

 

 

 

 

 

 

 

 

 

 

<너비우선탐색의 실행시간>

 

1.네트워크를 전체 탐색함(= 모든 정점을 따라 움직임)

 

-> O(간선의 개수)

 

2.탐색할 사람을 저장하는 큐가 있어야한다

 

큐에 사람을 추가하는데 걸리는 시간

 

-> O(1) (상수시간)

 

 

총 실행시간 O(사람(정점)의 수 + 간선의 수)

 

 

 

 

 

 

 

정리)

 

-너비우선탐색은 A에서 B까지가는 경로가 있는지 알려준다

 

-경로가 존재한다면 최단경로도 찾아준다

 

-그래프로 모형화하기

 

- 방향 그래프, 무방향 그래프 둘다 있을 수 있음

 

-탐색 목록에 추가된 순서대로 사람을 확인해야한다

 

- 한번 확인이 된 사람은 다시 확인이 되지 않게 해야한다

 

그렇지 않으면 무한루프에 빠질 위험이 있다 

 

 

 

[2023_01][산업정보화]_6_너비우선탐색.ipynb

0.47MB