꿈 꾸는 누렁이

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

일단 먼저 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 트리, 해쉬 테이블 등등 더욱 복잡한 것들은 지금까지 포스팅 한 것들을 복습한 이후에 조금씩 업로드를 진행할 것이다.

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

뭐 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에서의 순회라고 보면 된다. 그러기 위해서는 꼭 순서를 기록해야한다. 그렇지 않으면 순회에 비효율이 생길 수 있다. 이 때 사용하는 것이 큐이다

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

리스트 기반 큐는 뭐 간단하다. 그냥 일반 큐인데 연결 리스트로 이루어진 큐이다.

기본 형태는 다음과 같다.

매우 간단하다. 그래서 행복하다 

기본적으로 배열 기반의 큐와 똑같이 동작한다. 그러나 배열 기반 큐와 다른 점은 크기가 정해져 있지 않고 동적이고 가변이기 때문에 뭐, 꽉 찬 것으로 보이지만 비어있네, 마네 뭐 이런 배열 기반 큐의 치명적인 단점을 생각할 필요가 없다.

Front 노드 포인터를 통해서 가장 먼저 들어온 노드를 가리키며, 삭제 연산을 진행할 때마다 Front 노드 포인터를 한 노드씩 옮긴다. 그리고 Rear 노드 포인터를 통해서 가장 마지막에 추가된 노드를 가리키며, 삽입 연산을 진행할 때마다, Rear 노드 포인터를 새로운 노드로 갱신한다. 

삽입 연산

삭제 연산

꽉참/비어짐 확인 연산

꽉 찼는지는 연결 리스트이므로 확인할 필요가 없으니, 비어져있는 상태만 확인하면 되는데 이 역시 매우 간단하다.

메모리 관리

이번에는 연결 리스트 기반 스택으로 관리한다.

코드 및 실행 결과

드디어 원형 큐이다. 자기소개 페이지를 좀 작성하느라, 기록을 하지 못했다.. ㅎㅎ ㅠ.ㅠ

일단, 원형 큐이다. 지난 포스팅 기록에서 처럼 구조로 인해 어쩔 수 없는 단점과 문제를 가지고 있는 일반 배열 기반 큐에서 개선된 것이 원형 큐이다. 그 단점이자 문제는 다음과 같다.

아니 그러면, 삽입 인덱스와 꺼냄 인덱스를 모두 초기화 시켜서 다시 앞으로 옮겨오면 되는 것 아닌가? 라는 생각이 들었었는데 이를 반박할 수 있는 사례가 또 나타난다....

바로 이 경우이다. 순서대로 읽으면 된다. 35와 43 값을 추가 후, 배열의 끝이기 때문에 가정했던대로 삽입 인덱스를 초기화 시켜서 다시 삽입하여 공간을 활용하려는 노력이 보이는 그림이다. 그럼 만약에 위 상황에서 데이터를 순회하려면 어떻게 해야하는가?

7 -> 11 -> 15 -> 35 -> 43 으로 순회를 해야할까? 아니다. 이렇게 되면 큐의 기본 원리에 제대로 위배된다. 35와 43이 먼저 나와야한다. 

위 상황에서 큐의 기본 원리를 지키며 데이터를 순회하기 위해서는
1) 꺼냄 인덱스부터 먼저 확인 후 값을 꺼낸 뒤,
2) 다시 꺼냄 인덱스를 초기화하여 인덱스 0부터 들어간 값을 꺼내며 인덱스를 증가시키고,
3) 삽입 인덱스와 접하는지를 확인한다.
-> 2, 3 을 반복한다.

나 같으면 위와 같은 짓, 안 하겠다. 원형 큐에 대해 당장 알아본다.

먼저, 왼쪽과 같은 일반 배열을 오른쪽처럼 가상으로 구부렸다고 생각하고 모든 기록을 전개할 것이다. 기본 세팅에 대해서 좀 더 설명하자면, 다음 그림과 같다.

일반 큐처럼 삽입 인덱스와 꺼냄 인덱스가 존재하며, 이름이 각각 그림과 같이 달라질 뿐이다. 그리고 각 인덱스는 대입 연산이나 삭제 연산이 진행된 후에 증가하는 형태를 기본으로 한다.

그럼 삽입과 삭제는 그림 한 장으로 설명이 가능할 것 같다.

그렇다면 삽입을 하려면 큐가 꽉 찾는지 확인해야하며, 삭제하려면 큐가 비어있는지 확인해야한다. 원형 큐의 문제가 바로 이것이기 때문에 중요하다!!!!

먼저, 다음 그림을 보면 문제가 뭔지 알 수 있다

큐가 모두 비었을 때와 가득 찼을 때의 인덱스들의 상태가 완전히 똑같다. 인덱스의 위치에 상관없이 front가 rear을 따라 잡았다는 소리는 삭제를 모두 완료했다고 볼 수 있다. 그러나, rear이 front를 따라 잡았다는 소리는 삽입을 모두 완료했다고 볼 수도 있기 때문이다. 아주 기가 막힙니다.

그래서 원형 큐를 삽입할 때, 큐의 길이 - 1 만큼만 삽입하도록 할 예정이다. 꽉 찬 상태와 텅 빈 상태는 그림과 같다.

이 약속들만 지킨다면 원형 큐를 구현하면서 기가 막힐 일은 없을 것이다.

코드 및 실행 결과

----

----

그날 그날 정리하고 올려야 한다.. 묵혀두면 이렇게 고생한다.

-

오늘은 큐에 대해서 기록할 것이다. 큐는 굉장히 중요한 자료구조이다.

큐란 무엇인가?

비유해보자면 선착순이다. 먼저 온 사람이 먼저 서비스를 받는 것!

이를 두고 선입선출의 개념이라고 한다. 그림과 같이 나타낸다.

위 그림에서 옆으로 눕혀진 원통은 배열이라고 생각하면 된다. 배열에서 큐를 구현할 때를 생각해보자.

단순 배열 기반 큐에서의 삽입

단순 배열 기반의 큐에서 삽입 연산을 하는 것은 어려울 것이 없다. 배열의 끝에 값을 추가하듯이 인덱스를 증가시켜가면서 값을 넣으면 된다. 다음과 같이 말이다.

큐를 만들기 나름이지만, 인덱스를 증가시킨 후 삽입하는 것으로 하겠다.

단순 배열 기반 큐에서의 값의 꺼냄(삭제)

그러면 큐의 자료 구조 원칙에 맞도록 먼저 들어온 값을 꺼내려거든 어떻게 해야하나? 이런 경우는 삽입을 위한 인덱스를 하나 두고 증가시키면서 삽입을 진행하고, 꺼내려는 인덱스를 하나 두고 꺼내는 연산을 할 때마다 증가 시키면 된다!

삭제 또한 인덱스를 증가시킨 후 값을 삭제하는 것으로 하겠다.

큐의 꽉참/비워짐 여부 확인

큐를 가지고 삽입 / 삭제 연산을 진행하기 위해서 선행되어야 하는 연산은 큐가 비워졌는지 꽉 찾는지를 확인하면 된다. 아래의 그림은 큐의 비워진 상태를 나타대기 위해서 삽입은 멈추고, 꺼내는 연산만 한 그림이다. 

큐에 값이 꽉 찼음을 확인하는 방법은 선형 큐에서는 다음과 같다.

이 경우이다. 삽입 인덱스가 끝까지 가서 삽입 후 증가를 해야하는데 증가를 하려는데 증가가 안된다. 왜냐하면 인덱스가 끝에 왔기 때문이다. 이 경우 우리는 꽉 찼음을 확인한다. 

배열 기반 큐의 문제

위의 기록한 큐에는 문제가 있다. 다음과 같다.

이는 구조의 문제이다. -> 배열 길이가 정해져있고 순환하지 않는 선형이기 때문에 

이로 인해서 등장하는 것이 원형 큐이다!

원형 큐를 구현하면 선형 큐의 모든 개념 + 선형 큐의 문제 해결이 들어가기 때문에 선형 큐를 따로 포스팅하고 원형 큐에서 구현까지 마무리 지을 것이다.