[Algorithm] 이진트리 너비우선탐색(BFS : 배열 사용)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

ㅇ넓이우선탐색

  - 레벨 탐색이라고도 한다. (레벨순으로 탐색하기 때문에)

  - 가장 가까운 두 정점을 먼저 방문한다. 

  - Queue 자료구조를 사용한다. 

    Stack은 먼저 들어간 것이 나중에 나왔지만, Queue 는 먼저 들어간 것이 먼저 나온다.(선입선출이라고도 한다.)

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

#include<stdio.h> #include<vector> #include<algorithm>   using namespace std;   int Q[100], front=-1, back=-1, ch[10]; vector<int> map[10];   int main(){     int i, a, b, x;       for(i=1; i<=6; i++){         scanf("%d %d", &a, &b);         map[a].push_back(b);         map[b].push_back(a);     }       Q[++back]=1;     ch[1]=1;       while(front<back){         x=Q[++front];         printf("%d ", x);           for(i=0; i<map[x].size(); i++){             if(ch[map[x][i]]==0){                 ch[map[x][i]]=1;                 Q[++back]=map[x][i];             }         }     }       return 0; } Colored by Color Scripter

cs

이번에도 마찬가지로 그림을 그리면서 시뮬레이션을 해보자.

이번 문제에서는 배열을 사용하여 Queue 를 구현하였다.

line 13~17) 벡터 배열을 사용하여 인접리스트를 만든다.

   생성된 인접리스트를 그려보자면 아래와 같다.

line 19) 먼저 1번 노드를 Queue 에 넣어준다.

line 20) 방문한 1번 노드를 체크

초기 front = -1, back = -1

b

Q[]

0	1	2	3	4	5	6	7
1

ch[]

1	2	3	4	5	6	7
1

line 22) front 의 위치가 back 보다 작다면 Queue 에 더 빼낼 원소가 있다는 것이고,

          같아지는 순간 Queue 가 비어있는 상황이 된다.

line 23~24) 먼저 특정 정점과 연결된 정점을 찾기 위해 Q에 있는 원소를 빼내고 출력해준다.

    Queue 에서 원소를 빼거나 넣을 때는, ++front, ++back 을 해준다. 

f
b

Q[]

0	1	2	3	4	5	6	7
1

ch[]

1	2	3	4	5	6	7
1

line 26) 해당 정점과 연결된 정점을 인접리스트에서 찾는다.

line 27~29) 연결된 정점이 방문하지 않은 정점이라면, check 배열에 체크를 해준 후 Queue 에 해당 점점을 넣어준다.

여기서 1번 정점은 2번, 3번과 연결되어있으므로, 2번, 3번 정점을 체크해주고 Queue 에 넣어준다.

f
		b

Q[]

0	1	2	3	4	5	6	7
1	2	3

ch[]

1	2	3	4	5	6	7
1	1	1

그 다음 다시 line 22 의 while 문이 돌고,

2번 정점을 Queue 에서 빼내고 2번 정점과 연결된 정점을 찾아서 방문하지 않았으면 Queue 에 넣어주고 체크해준다.

	f
				b

Q[]

0	1	2	3	4	5	6	7
1	2	3	4	5

ch[]

1	2	3	4	5	6	7
1	1	1	1	1

다음도 마찬가지로  line 22 의 while 문이 돌고,

3번 정점을 Queue 에서 빼내고 3번 정점과 연결된 정점을 찾아서 방문하지 않았으면 Queue 에 넣어주고 체크해준다.

		f
						b

Q[]

0	1	2	3	4	5	6	7
1	2	3	4	5	6	7

ch[]

1	2	3	4	5	6	7
1	1	1	1	1	1	1

그 다음도 마찬가지로 front 가 back 보다 작으므로 while 문이 계속 돌아갈 것이다.

이번엔 4번 정점을 Queue 에서 빼낸다. 하지만 4번 정점과는 연결된 정점이 없으므로 line 26 의 for문은 넘어갈 것이다.

			f
						b

Q[]

0	1	2	3	4	5	6	7
1	2	3	4	5	6	7

ch[]

1	2	3	4	5	6	7
1	1	1	1	1	1	1

..

5번, 6번, 7번 정점도 마찬가지로 연결된 정점이 없으므로 line 26 의 for문을 넘어가고

이제는 front == back 의 상황이 왔으므로 Queue 에는 모든 원소가 빠져나갔을 것이다.

						f
						b

Q[]

0	1	2	3	4	5	6	7
1	2	3	4	5	6	7

ch[]

1	2	3	4	5	6	7
1	1	1	1	1	1	1

이렇게 Queue 를 배열로도 구현할 수 있었다.

약간 복잡하긴 하지만 시뮬레이션을 돌려보니까 그래도 나름 쉽게 이해할 수 있었다.

하핳

#. Result

  - Input --------------------------------------------------------

1 2 

1 3 

2 4 

2 5 

3 6 

3 7

------------------------------------------------------------------

  - Output --------------------------------------------------------

1 2 3 4 5 6 7

------------------------------------------------------------------