깊이 우선 탐색 / 넓이 우선 탐색 + 그래프를 알고리즘상으로 표현하기

++참고 인프런 이재규님 강의 

깊이 우선 탐색은 depth first search라고 해서 DFS라고 불리우는 탐색법이다.

그래프의 모든 정점들을 효율적으로 방문하기 위한 알고리즘이며 여러가지 결과가 나올 수 있다.

현재 방문한 정점에 연결된 정점 중 방문하지 않은 정점을 방문한다. 재귀적인 특성을 가지고 있고 스택을 활용해서 재귀호출을 제거 할 수 있다.

넓이 우선 탐색은 breadth first search라고 해서 BFS라고 불리우는 탐색법이다.

깊이 우선 탐색과 마찬가지로 그래프의 정점들을 순회하기 위한 알고리즘이며 여러가지 결과가 나올 수 있다.

현재 방문한 정점에 연결된 모든 정점을 한번씩 방문한다. 더 이상 현재 정점에 연결된 정점 중 방문하지 않은 정점이 없을 때, 다음 정점으로 이동해서 같은 과정을 반복한다.

말로하니까 좀 복잡하게 들리니 컴퓨터 c드라이브에 있는 수많은 폴더들을 열어본다고 가정해보자

깊이 우선 탐색은 더 이상 열 수 있는 폴더가 없을 때 까지 계속 폴더 안의 폴더를 열어보는 방식이다. 결국 폴더안에 새로운 폴더가 없으면 

뒤로 가기를 눌러서 새로운 풀더를 열고 그 안에서 같은 방법을 반복하는 방식이다.

넓이 우선 탐색은 우선 c드라이브에 있는 모든 폴더를 하나씩 열어본다. 그런 다음에 그 중에서 폴더 하나를 골라 들어가서 또 그 안에 있는 폴더를 전부 열어본다. 

깊이우선 탐색은 주로 그래프 내의 특정한 경로를 찾을 때 사용되는 것 같고(최단경로라든지 미로찾기 등)

넓이 우선 탐색은 걍 빽트래킹 땜빵용 알고리즘임. 특히 공간채우기 문제같은거 (뇌피셜)

그럼 그래프를 표현하고 깊이우선 탐색법과 넓이우선 탐색법으로 돌아보자.

그래프를 표현하는 방법은 2가지가 있다. 하나는 그냥 간단하게 2차원 배열을 만들고 각각의 정점들을 X, Y축에 대응시켜서 사이에 간선이 있는지 없는지를 표현하는 방법이다.

다른 하나는 정점들을 연결리스트배열로 표현하는 방법이긴 한데 솔직히 그냥 첫번째 방법이 더 직관적이라고 생각하기 때문에 2번째는 사용하지 않겠다.(연결리스트 만들기 귀찮은거 안ㅂㅁ..)

예시로 표현하면  다음과 같다,

이렇게 생긴 그래프가 있다고 하면 간선 배열은

    1 2 3 4 5 

1   0 1 0 1 0

2   1 0 1 1 0

3   0 1 0 0 1

4   1 1 0 0 1

5   0 0 1 1 0  

이렇게 그려지는 것이다. 지금은 그냥 단순한 양방향 그래프이기 때문에 그래프를 대각선으로 봤을 때 대칭이다.

가치를 계산하려면 1이 아닌 가치를 입력하면 되고 방향성을 추가하기 위해선 대칭을 무시하고 한쪽으로만 간선을 놓으면 된다.

다음은 그래프를 깊이 우선 탐색하는 코드다.

따로 설명 할 필요 없이 간단하게 재귀호출로 구현했다. 그래프에 방향성이나 가치망이 없기 때문에 그냥 단순하게 경로만 출력하도록 구현했다.

이렇게 움직였다. 

다음으로 넓이 우선 탐색을 구현하고 깊이 우선이랑 뭐가 다른지 보자

넓이 우선탐색을 구현할때는 큐(queue)라는 자료 구조를 사용한다.

깊이 우선 탐색에 비해서 살짝 복잡하지만 천천히 보면 이해할 수 있다.  깊이 우선 탐색은 연결된 정점으로 들어가고 보는 느낌이었다면 넓이 우선 탐색은 연결된 정점을 큐에 다 담고 그 다음에 들어가는 느낌이다.

(그림과 실제 인덱스가 1차이 나니 주의해서 보기)

이런 순서로 방문한다. 다음 포스팅에서는 방향성과 가중치를 포함해서 문제다운 문제를 풀어보겠다. 

2019.04.02 간선 배열 오타 수정. 보다가 깜짝놀람..