이진트리 넓이 우선 탐색(DFS)

pa324·2019년 10월 21일
0

이진트리 넓이 우선 탐색(BFS)

넓이 우선 탐색(BFS)란?

  • 루트노트에서 출발을 한다. (1번노드)
  • 루트노드에서 이동할 수 있는 모든 노드를 방문 한다. (2번노드,3번노드)
  • 루트노드에서 2번이동해서 갈 수 있는 노드들은 한번에 갈 수 있는 노드들과 연결되어 있다 (4번,5번,6번,7번 노드)
  • 2번만에 갈 수 있는 노드들을 방문한다.
  • 1번,2번,3번,4번,5번,6번,7번 순으로 노드를 방문한다.
  • BFS는 레벨탐색으로도 불린다. (level순으로 탐색하기 때문이다.)
  • BFS는 Queue자료구조를 활용해서 구현할 수 있다.
    • Queue 자료구조는 Stack과는 다르게 First in First Out의 특징을 가진다.
      • 들어가는 입구와, 나오는 출구가 따로 있다.
      • 먼저 들어간 자료가, 먼저 나가게 된다.

Queue를 이용한 BFS

  • 1번노드를 Queue에 push 하면서 pop 한다(pop하면서 출력)
    • 1번을 출력하면서, 1번노드와 연결된 노드들을 queue에 push 한다.
      • 2번,3번 노드가 queue에 들어간다.
  • queue에서 2번을 pop 하면서 출력하고, 2번과 연결된 노드를 push 한다.
    • 4,5번 노드가 queue에 push 된다.
      • 현재 Queue의 상태는 (3,4,5)이다.
  • queue에서 3번을 pop 하면서 출력하고, 3번과 연결된 노드를 push한다.
    • 3번과 연결된 6번,7번 노드를 push
      • 현재 Queue의 상태9(4,5,6,7)
  • queue에서 4번을 pop 하면서 출력하고, 연결된 노드가 있는지 확인한다.
    • 연결된 노드가 없으니 바로 출력
  • 5번,6번,7번 노느도 연결된 노드가 없으니 바로 출력한다.

BFS 코드구현

#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;
}

BOJ 1697 숨바꼭질 6

문제

풀이

  x-1, x+1, x*2인경우로 DFS를 하면 된다. 이때, 범위를 초과하지 않도록 해야 시간복잡도가 줄어든다.
 문제에서 좌표값이 양의값이면서 100,000보다는 작아야 하므로 해당범위에 포함되지 않는 값들은 탐색하지 않도록 조건문을 처리해야 한다. (N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다)

코드

#include<stdio.h>
#include<queue>
using namespace std;
int visited[100001];
queue<int> q;
int time = 0;

void bfs(int n, int m) {
	
	q.push(n);
	visited[n] = 1;

	while(!q.empty()){
		int size = q.size();
		for(int i = 0; i <size; i++) {
			int x = q.front();
			q.pop();
			
			if(m == x) {
				printf("%d",time);
				return;
			}
			if(x-1 >=0 && visited[x-1] != 1) {
				q.push(x-1);
				visited[x-1] = 1;
			}
			if(x+1 <= 100001 && visited[x+1] != 1) {
				q.push(x+1);
				visited[x+1] = 1;
			}
			if(x*2 <= 100001 && visited[x*2] != 1) {
				q.push(x*2);
				visited[x*2] = 1;
			}
		}
		time++;
	
	}
}
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	bfs(n,m);	
	return 0;
}
profile
안녕하세요

0개의 댓글