꿈 꾸는 누렁이

앞선 내용들을 바탕으로 진행하기 때문에 읽고 나서 읽는 것을 추천한다. 설명을 잘 하지 못해서 읽어도 모를 수도 있다. 이 글들은 복습을 위한 기록이니, 잘 못 알아 듣겠으면 다른 곳 가서 읽기를 권한다ㅋㅋㅋㅋ ㅜㅜ

일단 먼저 BFS가 뭔지에 대한 내용은 위 링크 중 땡땡 우선 탐색이라는 글에 좀 더 자세하게 정리되어 있고, 이 글에서는 BFS 방법으로 순회하는 과정을 나타낼 것이다.

중요 핵심

일단 너비 우선 탐색은 깊이 우선 탐색과 달라도 너무 다르다. 현재 정점 하나에 연결되어 있는 모든 정점에 순회를 해야하다보니 현재 정점에 연결된 각 정점마다 순서를 매겨서 기록해야 한다.

깊이 우선 탐색은 현재 정점에서 다음으로 갈 타겟을 정하기만 한다면 정점 방문(순회)과 현재 정점의 갱신이 한 번에 발생한다. 

그러나 너비 우선 탐색의 경우에는 정점 방문이라는 개념을 좀 더 확장해야한다. 단순히 방문만 하는 것이 아니라, 방문 후에 방문한 해당 정점을 큐 자료 구조에 넣는 작업까지가 정점 방문이라고 생각해야한다.

그리고 정점 방문과 현재 정점의 갱신이 동시에 발생하지 않는다. 정점 방문과 현재 정점의 갱신을 동시에 해버리면 나머지 연결되었던 정점에 접근할 기회가 박탈된다.

위의 예에서 현재 정점이 0이고 (ㄱ, ㄴ)처럼 1 정점을 방문한 뒤 바로 현재 정점으로 갱신을 해버리면 0 정점에 연결되어 있던 2 정점에 접근할 수 있는 기회가 사라진다. 그렇기 때문에 정점의 방문과 현재 정점의 갱신이 동시에 발생하지 않는 것이다. 

이러한 이유 때문에 진짜 설명하기에 겁~~나 헤깔린다. 이러한 핵심적인 특징을 인지한 상태로 프로세스를 봐야한다.

순회 프로세스

먼저 다음과 같은 그래프에서 순회를 시작할 것이다.

정점 0은 시작 정점이므로 일단 방문 처리가 자동으로 된다. 정점 방문에 해당하는 부분이 순회라는 표현이고, 이는 접근 + 큐 기록 까지를 의미한다. 접근했다는 의미 또한 방문 Flag 배열에 값을 갱신하는 조작을 의미하는 것이다.

현재 정점에 연결된 모든 정점을 순회하는 과정이다.

현재 정점인 0 정점에 연결된 모든 정점에 대해서 순회가 완료되었으니, 큐에서 값을 꺼내서 그 값을 현재 정점으로 갱신하고, 다시 순회를 시작한다.

그리고 큐에 정점이 여전히 존재하므로 다시 큐에서 값을 빼내어 현재 정점을 갱신하고, 순회를 재시작한다. 그런데 2 정점 같은 경우는 순회 가능한 인접 정점이 없으므로 그냥 나가리~

큐에 정점이 여전히 존재하므로 다시 큐에서 값을 빼내어 현재 정점을 갱신하고, 순회를 재시작한다. 4 정점이 마지막 정점이긴 하지만 그림을 한 눈에 보는 우리나 아는 것이지 컴퓨터는 4 정점이 마지막 이라는 것을 아직 모른다! 그렇게 때문에 4 정점이 마지막이어도 원래 규칙대로 큐에 넣는다.

큐에 정점이 아직 존재하니 뽑고, 뽑힌 값으로 현재 정점을 갱신한다. 그런데 현재 정점에서 순회를 하려고 보니, 순회 가능한 인접 노드가 없다. 

그렇게 더 이상 큐에 값을 넣지 못하고, 큐가 비었으므로 모든 그래프를 순회했으므로 종료한다. 

0 -> 1 -> 2 -> 3 -> 4 순으로 순회가 이루어졌다.

진짜 뇌리에 박히겠다 박히겠어 정말 ㅋㅋ

이제 관련된 부분 코드를 보도록 하겠다.

코드 분석

큐가 새롭게 사용되므로 큐에 대한 코드가 필요한데 이미 만들어놓았던 배열 기반의 큐 코드를 활용할 것이다. 그런데! 그냥 큐는 배열 관리가 까다롭기 때문에 더 효율적인 배열 기반의 원형 큐를 사용할 것이다!

깊이 우선 탐색 코드에 대해서 바뀌는 부분과 추가되는 부분을 기록하겠다.

너무나도 기쁘게도 이거 하나가 변경된다.

ㄱ~ㅅ 순서대로 읽으면 된다.

전체 코드 및 실행 결과

전체 코드는 배열 기반의 원형 큐와 연결 리스트 BFS로 인해 변경된 그래프 코드 순으로 업로드를 하겠다.

배열 기반의 원형 큐 ArrayBasedCircleQueue.h -- -- -- -- -- 

연결 리스트 linkedlistforgraph.h -- -- -- -- --

BFS 로 인해 변경된 그래프 코드 BreadthFirstSearchGraph.cpp -- -- -- -- --

아래는 실행 결과이다.

이 두 탐색을 이용한 최소 비용 신장 트리 부터 해서 트리 부분의 AVL 트리, 해쉬 테이블 등등 더욱 복잡한 것들은 지금까지 포스팅 한 것들을 복습한 이후에 조금씩 업로드를 진행할 것이다.

그노므 DFS! DFS! 드디어 깔끔하게 정리를 한다. 이 탐색 기법 하나에 워낙 들어가는 내용이 많기 때문에 바로바로 정리하지 않으면 다시 처음부터 공부하는 수준으로 공부를 해야한다 흑흑...

이전의 포스팅의 내용을 기반으로 작성되기 때문에 이전 부분을 포스팅을 참고하라고 올려놓겠다.

중요 핵심

일단은 깊이 우선 탐색은 아래 세 가지가 핵심이다.

1. 깊이 접근하는 것
2. 왔던 경로를 되돌아오는 것
3. 정점 방문 여부를 기록하는 것

이 세 가지를 핵심으로 기록하겠다. 사용되는 예시는 간단하게 다음과 같다.

첫 번째, 깊이 접근한다는 것은 한 정점에서 연결되어 있는 정점 중 하나의 정점을 선택해서 파고 들어가고 또 그 정점에서 연결된 정점 중 하나의 정점을 파고 들어가는 식의 방법을 이야기 한다.

1로 갈지, 2로 갈지는 중요하지 않다. 0이라는 정점에 연결 되어 있는 정점이 1 먼저 연결되있는지, 2 먼저 연결 되어있는지에 따라 다르다. 즉, 정점의 연결 정보를 나타내는 연결 리스트의 정렬 구조에 따라서 1 노드와 2 노드 중 어떤 것을 선택하게 될지 결정된다는 소리이다. 어찌됐건 우리는 순회 하는 것이 목적이므로 어딜 먼저 방문하는지는 의미가 없다.

두 번째, 왔던 경로를 되돌아오는 것은 되돌아오면서 놓친 정점을 순회해야하는 것이다. 이 때 경로를 다시 되돌아오려면 경로를 일단 기록을 해야하는데 역행이므로 스택의 형식대로 기록하면 된다. -> 방문 추적을 목적으로 스택을 사용한다.

세 번째, 정점 방문 여부를 기록한다는 것은 일반 순차 배열을 이용하여 기록한다. 다음 그림에 설명을 포함시키겠다.

주요 3가지 핵심에 대해서 살펴보았고 이번엔 그 순서대로 그려볼 것이다...

순회 프로세스

시작 정점 0을 방문된 상태로 시작한다. -> 방문 Flag 배열에서 정점 0을 True 처리.

연결된 인접 정점은 1 정점과 2 정점인데 방문 Flag 배열을 봐도 방문 처리가 False이기 때문에 두 정점 모두 접근이 가능하다. 이 예에서는 2 정점을 방문하겠지만 1 정점으로 방문해도 순회 순서만 다를 뿐 다른 의미는 없다.

2 정점을 방문하면서 방문 Flag 배열에서 2 정점을 True(방문) 처리하고, 떠나온 0 정점은 다시 돌아가기 위한 발자국으로 남기기 위해서 스택에 넣는다.

위와 마찬가지 과정을 통해 2 정점을 떠나면서 스택에 2 정점을 넣고, 3 정점을 방문한 뒤 방문 Flag 배열의 3 정점에 대한 방문 여부를 True로 변경한다.

또 마찬가지로 같은 과정을 반복하는데 3 정점에서는 1 정점과 4 정점에 접근 가능하다 어디로 가든 상관없지만 이번 예에서는 4 정점에 방문할 것이다.

4 정점에서는 인접한 정점이 모두 방문 처리 되었으므로 이제 스택에서 값을 POP 함으로써 되돌아 가면서 그냥 지나친 정점을 탐색한다.

3 정점으로 돌아왔을 때, 보니까 1 정점을 방문하지 않고 그냥 지나쳤었기 때문에 1 정점에 방문한다. 이 때, 1 정점에 방문하기 위해서 3 정점을 떠나는 것이니 1 정점 방문 이후 다시 돌아오기 위해 3 정점을 다시 스택에 넣는다. 그리고 1 정점에 대한 방문 처리를 진행한다.

그리고 1 정점에서 인접 정점 모두 방문 처리 되었으니 Pop을 통해 돌아가고, 3 정점에서도, 2 정점에서도 마찬가지로 인접 정점 모두 방문처리 되었으므로 Pop을 통해 돌아가다가 0 시작 정점까지 Pop하여 스택이 빈 경우 비로소 모든 순회가 끝난 것이다.

0 -> 2 -> 3 -> 4 -> 1 순으로 순회가 이루어졌다.

진짜 뇌리에 박히겠다 박히겠어 정말 ㅋㅋ

이제 관련된 부분 코드를 보도록 하겠다.

코드 분석

스택이 새롭게 사용되므로 스택에 대한 코드가 필요한데 이미 만들어놓았던 배열 기반의 스택 코드를 활용할 것이다. 스택 설명 기록은 아래의 링크에서 확인하면 된다.

먼저 바뀌는 부분과 추가되는 부분이다.

그래프 내의 방문 Flag 배열이 추가 된다.

방문 처리를 수행하는 함수가 추가된다.

깊이 우선 탐색을 수행하는 함수이다.

한 함수이지만 라인 수를 맞춰서 읽으면 된다... 이전 자료구조인 스택에 대한 사용 방법 또한 익혀야 하고 너무나도 추상적이라서 용어 설명이 너무 어려운 것 같다..ㅠ.ㅠ

그래프 종료 및 메모리 공간 해체 관련 코드이다.

전체 코드 및 실행 결과

전체 코드는 배열 기반의 스택과 변형된 연결리스트(오름차순으로 노드를 삽입; 이전에는 그냥 삽입했다.), DFS로 인해 변경된 그래프 코드 순으로 업로드 한다.

배열 기반의 스택 ArrayBasedStack.h -- -- -- -- --

변형된 연결 리스트 linkedlistforgraph.h -- -- -- -- --

DFS로 인해 변경된 그래프 코드 DepthFirstSearchGraph.cpp -- -- -- -- --

일단, 위의 그래프 기본들을 기반으로 작성되기 때문에.. 링크해둔다.

뭐 BFS니 DFS니 이상한 용어 써가면서 아는 척 오졌던 학과 동기들 보면 이제 이렇게 생각하라. 

대단한 친구들이네

근데 사실, 이상한 용어가 나와서 오히려 겁 먹고 어려울지 모르겠지만 조금만 이해하면 그렇게 어렵지 않다. 

BFS 나 DFS 모두 Search의 일종이다. 뭐 말로만 Search지 순회다 순회. 순회하면서 원하는 값이 나오면 조건문으로 캐치하면 그게 Search이지 무엇이겠는가?

아무튼 두 개념 모두 순회인데, 순회하는 방법이 다르다. 그래서 두 가지를 모두 동시에 기록해 두려고 한다.

DFS (Depth First Search)

DFS는 Depth First Search 로 깊이 우선 탐색이다. 말 그대로 우선적으로 그래프를 깊게 깊게 파고 들어간다는 것이다. 그렇게 전부 파고 들어 갔다면 다시 되돌아 나오면서 깊게 파면서 놓쳤던 주변을 살펴보며 나오는 형식이다.

위 그림과 같은 식인데, 윤성우 교수님의 자료구조 책에서는 다음과 같이 표현한다. "너니까 이야기해주는거야" 하면서 깊고 친한 관계라고 생각하는 친구들에게만 비밀 이야기를 전달한다. 그러다보니 3번과 같은 정점에게도 퍼져있는 비밀 이야기가 소문이 나는 상황에 비유를 하셨다ㅋㅋ

중요한 것은 돌아 나오는 것과 각 정점들의 방문 여부이다. 이 둘을 어떻게 관리하고 코드로써 표현할 것인지가 큰 쟁점이다.

첫째로 돌아 나온 다는 것은 그 발자취를 기록하면 된다. 기록할 때 그냥 순서대로 기록하고 기록한 순서대로 다시 보는게 아니라 돌아나가는 것은 역재생하는 것과 같으므로 스택 자료구조를 이용한다.

둘째로 정점들의 방문 여부는 인덱스 값과 정점 값을 매칭 시킨 flag 역할을 1차원 배열로 처리를 하면 된다.

참고>>

이런 경로 또한 가능하다. 구현해 보면 알겠지만 하나의 정점에 연결된 정점들 중 어떤 것을 선택하는지에 대한 로직은 순회 로직에 들어가지 않는다. 그러니까 시작 정점에서 왼쪽 정점으로 갈지, 오른쪽 정점으로 갈지를 중요시 하지 않는다는 소리이다. 이는 정점간 연결을 나타내는 자료구조 내에서 어떤 순서로 연결 정보를 저장했는지에 따라서 다르게 나온다. 그니까 어떤 경로든 해당 탐색의 기본 원리에만 들어 맞다면 경로 순서의 맞고 틀리고를 따지는건 의미가 없다는 소리이다.

BFS (Breadth First Search)

반면에 BFS는 Breadth First Search 로 너비 우선 탐색이다. 말 그대로 우선적으로 넓게 넓게 퍼뜨리며 그래프를 파고들겠다는 것이다. 그러니까 어떤 정점을 순회하기만 했다 하면 바로 그냥 그 해당 정점에 연결된 모든 정점에게 방문하는 것이다. 

이건 약간 예로 들자면, 정책 발표에 따른 메시지 퍼짐이다! 출발 지점에서 정책을 발표한다. 그 양 옆 정점은 그 해당 정책을 티비를 통해 실시간으로 들은 정점들이고, 그리고 나서 그 실시간으로 들은 정점들이 지인을 만날 때마다 그 정책에 대해서 이야기하는 모습 같다고 비유할 수 있다.

중요한 것은 방문/순회 차례에 대한 기록과 각 정점들의 방문 여부이다. 이 둘을 어떻게 관리하고 코드로써 표현할 것인지가 큰 쟁점이다. 

첫째로 물론 각 정점들의 방문 여부는 위에서와 마찬가지로 flag 역할의 1차원 배열로 충분하다. 

둘째로 방문/순회 차례에 대한 기록은 위 DFS와는 조금 다르다. 방문한 정점과 연결된 정점들을 모두 방문하고, 그 다음 순서까지 정한 뒤 넘어가야헌다 그것이 BFS에서의 순회라고 보면 된다. 그러기 위해서는 꼭 순서를 기록해야한다. 그렇지 않으면 순회에 비효율이 생길 수 있다. 이 때 사용하는 것이 큐이다

이렇게 두 개념을 코드를 통해 구현해 볼 것이다 

드디어 그래프의 기본 코드이다.

이전 포스팅에서 설명했듯이, 그래프를 표현하는 방법 중 인접 리스트 방법을 이용하여 기본적인 그래프를 구현해 볼 것이다. 그 인접 리스트에 해당하는 방법 또한 이미 이전에 포스팅 한 코드를 기반으로 만들 것이다. 해당 리스트 코드는 따로 첨부하도록 할 것이다.

먼저, 그래프를 만드는데 있어서 연결 리스트 자료구조를 이용한다. 그래서.. 하 골치 아프게거니 하다가 C++ STL의 리스트를 그냥 활용할까 했는데, 그래도 내가 전에 만든거 테스트도 할 겸, 그걸로 하자! 라고 생각해서 내가 만든 리스트를 100% 신뢰하며 쓰기로 결정했다. 

이미 구현된 자료구조는 100% 신뢰하며 쓰는 것이 국룰이다.

그래프 초기화 및 정점 추가

그래프를 초기화 한다는 것은 코드 작성자 나름이고 기능에 따라 더 무언가 있겠지만, 나는 정점을 추가하는 용도로 사용되었다. 

간선 추가 

이런 식으로 간선이 연결되며 연결된 그래프의 모양은 대충 다음과 같다.

그래프 출력

각 정점 노드 별로 리스트 내에 제공하는 show 관련 함수를 이용하여 출력을 해주면 된다!

출력 결과는 다음과 같다.

리스트 구현할 때, 헤드 부분을 바보 같이 잘못 이해하고 잘못 구현했었다.. 그냥 가리키는 포인터로 두면 될 것을 노드로 처리해버려서.. 아무튼 노란 부분은 무시해도 전혀 문제 없다.

그래프 소멸

그래프가 겁나 어려울 줄 알았는데 생각보다 구현하기 쉬웠다. 다만 탐색에 대한 부분들이 들어가 있지 않기 때문에 모르고 하는 소리일 수 있으나, 진짜 생각했던 것 만큼 어렵지는 않다. 다만 그래프는 이전 자료구조들을 많이 활용하기 때문에 처음부터 구현하기에는 조금 까다로운 것은 사실이다.

다음 포스팅은 탐색에 대해서 하나하나 기록해볼 것이다.

---

코드들이다. 그래프 실행 결과는 이미 위에 있기 때문에 코드만 업로드한다.

그래프 코드

리스트 자료구조 헤더 코드

드디어 그래프에 대한 포스팅이다. 여러가지 병행하며 정리할 것도 너무 많아서 ㅋㅋ 미루고 미루다 이제 올리게 된다. 오늘은 그래프의 기본 중에 기본인 용어 및 정의 정리이다.

그래프란?

먼저, 그래프란 아래의 설명과 같다.

비선형 자료구조, 즉, 트리 또한 그래프의 일종이라는 것을 알 수 있다!

이러한 그래프에는 간선의 방향성이라든가, 가중치, 부분 집합에 따라서 그래프의 종류가 나뉜다 이를 하나씩 나열해 볼 것이다.

무방향 / 방향 그래프

간선에 방향이 없고, 있고의 차이이다.

완전 그래프

정점 별로 모든 정점과 연결되어 있는 그래프를 완전 그래프라고 하는데, 이 때, 방향 완전 그래프는 무방향 완전 그래프보다 간선의 수가 2배 많다.

가중치 그래프와 부분 그래프

가중치 그래프는 간선에 가중치를 두고, 예를 들어, A에서 C로 가려면 3+1 혹은 4+5 비용이 든다고 표현할 수 있다. 부분 그래프는 말 그대로 그래프의 부분만을 그려낸 것이다.

그래프의 집합 표시

이러한 그래프를 집합 형태로 표현을 할 수 있다

그래프를 코드로 표현하기 위한 약속

그래프는 진짜 들쑥 날쑥인데 어떻게 표현하지 싶었는데, 사람들은 참 머리가 좋은 것 같다.

그래프가 어떻게 생겼든, 크기가 어떻든 정점 사이가 얼마나 멀든 좁든 간에 각 정점과 그 사이의 간선만 표현할 수 있다면, (예를 들어 어느 점과 어느 점이 어떤 선으로 연결되어 있는지 등의 정보) 오케이이다.

그 정점과 간선 등의 관계를 표현하는 방법은 위 그림에서처럼 인접 행렬, 인접 리스트가 그 방법이다. 방법은 그림으로 보는 것이 자세하고 편해서 그림으로 표현을 해 보았다.