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

넓이 우선 탐색(BFS)란?

image.png

  • 루트노트에서 출발을 한다. (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

문제

image.png

image.png

풀이

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