dfs/bfs 정리(3)

드디어 dfs/bfs는 끝이다!

 

이글에서는 DFS/BFS가 대략적인 내용을 설명하고

내 나름대로 DFS와 BFS를 분석한 내용을 말하려고한다.

두개의 공통점은 DFS나 BFS둘다 그래프를 이용하는 알고리즘이다.

하지만 극명히 달리는 차이점이 있는데, 그건 바로 값을 어떻게 읽는지가 다르다.

즉, DFS는 스택형식으로 값을 읽고

BFS는 큐형식으로 값을 읽는다.

스택과 큐를 잘 모르시는 분들은

2020/09/03 - [알고리즘/코테 알고리즘 정리 노트] - dfs/bfs 정리(1)

dfs/bfs 정리(1)

를 참조하면 될 것 같다.

그림을 그려보자.

이런 그래프가 있다고 하자.

그러면 DFS와 BFS를 하나하나 비교해가면서 어떻게 다른지 확인해 보자.

먼저 DFS.

DFS는 깊이 우선 탐색으로 무조건 깊이만 게 핵심이다.

이게 무슨 뜻이면

1의 작성된 공(노드)를 기준으로 보면 세가지 길이 존재한다.

그러면 먼저 우리는 세 가지길중에서 어떤 선택해야한다.

예를들어

 

이 길을 선택했다고 하자.

그러면 다른 길은 일단 갈수 없다.(어차피 나중에 가기 때문에 상관없다.)

2번공은 갈 수 있는 길은 하나 뿐이다. 그렇기 때문에 

 

이렇게 하면 이 길의 탐색은 종료하게 된다.

그러면 DFS는 끝인가? 그렇지는 않는다. 바로 다시 위로 하나씩 올라간다.

만약 다른 길이 존재하면 그 길로 가야 하기 때문이다.

2번길에도 없구,

1번 길에은 아직 길이 2개나 존재한다.

이제 이와 같은 방법을 반복하면 DFS가 완료된다.

대략적으로 

  이건 인덱스로 나타냈다.

 그렇기 때문에 항상 값이 나오는 것은 아니다.

다르게 나온다.

 

 

 

이건 인덱스로 나타낸게 아닌 크기 값이라 할 수 있을 것 같다.

즉, 2번은 1번다음 이라는 뜻이기 때문에 1보다 큰 2로 설정해두었다.

 

 

다음 BFS도 마찬 가지로 같은 그래프로 해보겠다.

 

BFS는 너비 우선 탐색으로 너비로 탐색한다는 뜻이다. 너비로 탐색한다는 게 무슨 뜻일까?

간단히 말해 1번 노드는 3가지 길이 존재한다고 위에서 언급했다.

즉, 위 세개의 노드의 너비는 2이다. 왜냐하면 첫번째 노드와 지금 구하려는 노드의 갯수를 뜻한다.

노드가 2개

이것을 위와 같은 방법으로 하게 되면

이런식으로 값이 나타나게 된다.

인덱스로 확인 할때는 값이 다르게 나온다. 

 

근데 우리는 여기까지는 잘 알고 있다. DFS가 뭔지 BFS가 뭔지

문제에서는 이렇게 노드와 그래프 형식으로 문제가 출제가 되지 않는다.

보통은 이런식으로 표형식으로 정해진다.

간단한 2개의 그림으로 설명해보자.

이 그림은 BFS를 나타낸 그림이다. 여기보면 작대기 하나로 결정하는데

여기서 작대기는 다음 노드와 서로 통신을 하겠다는 뜻이다.

마치 바이러스가 퍼지는 것 처럼 서서히 최후까지 가게 되는 탐색법이다.

모든 그림을 다그리지는 않았지만 마지막은 아마 14가 나올 것 같다.

이건 DFS인데 조금더 다채롭다 보면 색깔이 전부 다르다. 그리고 이상한 곡선이 2개나 존재한다 이게 뭘까?

DFS의 특징은 한곳을 선택하면 다른 곳은 신경쓰지 않는다. 

예를들어, 초록색 길을 선택한다고 하면 아래로 끝까지 간다.

만약, 끝을 도달하게 되면 다시 위로 올라간다. 어디까지 올라가냐 하면

사실은 6까지만 올라가도 상관없다. (7에서 값을 결정해도 된다.)

하지만 그냥 0까지 올라갔다. 왜냐하면 그냥...

DFS특징이 더이상 값 탐색이 불가능할 경우, 탐색이 가능한 위치까지 올라간다.

이것을 스택에서 값을 빼는 행위라고 할 수 있다.

올라가서 다른 방향으로 탐색하고 탬색 이 안되면 다시 되돌아가는 식으로 하게 된다.

 

근데 어째서 BFS가 최소값을 구하는데 더 유리할까?

위의 마지막 값은 같은데 말이다.

BFS는 장애물이 있으면 그 값을 가지않고 다른 값 대신 가게되지만

DFS는 장애물을 만나게 되면 재 탐색하기 때문에 

BFS가 더 빠른것 같다.(여기는 뇌피셜)

 

드디어 DFS/BFS 정리가 끝났다.

위 표는 나중에 큐와 스택을 재대로 접목해서 설명해봐야겠다.