Breadth First Search

그래프의 정점들을 탐색하는 알고리즘에는 대표적으로 DFS와 BFS가 있다.

 

🕵️설명해본다

BFS는 넓이 우선 탐색으로 👭🏿가까운 정점부터 먼저 다 탐색하러 간다.

시작 정점의 인접한 정점을 다 탐색한 후, 다시 방문한 정점들의 인접한 정점들을 탐색하러 가는 방식이다.

DFS보다 짧은 시간안에 최단거리 찾는 것을 보장한다.

 

🕵️구현해본다

넓게 넓게 탐색해야 하므로 큐, 반복문으로 구현한다.

• 시작 정점 혹은 어떤 정점에서 갈 수 있는 자식 정점 경우를 생각한다.
• 반복문을 돌며 큐에서 정점을 빼고, 그 정점의 자식들을 다시 넣고 빼고를 반복한다.
• 큐에 자식들을 넣을 때 범위, 목표 도착 등을 체크한다. (체크했을 때 갈 수 없는 자식 정점은 큐에 넣지 않는다)
• 큐에 넣을 정점 형태는 '정점 식별(Value) - 들어간 깊이(Count)' 로 하고 큐에 자식들을 넣을 때 Count를 +1 해준다.

 

🕵️코드코드

백준 1697번은 1차원 위치 A에서 1차원 위치 B로 이동하는 가장 빠른 시간을 찾는 문제이다.

 

이동 방법은 +1, -1, *2 로 어떤 정점에서 이동할 수 있는 3가지 정점을 자식 정점이라고 생각한다. 반복문을 돌면서 큐에서 정점을 빼고 다시 그 정점에서 갈 수 있는 3가지 자식 정점 중에서 목표 정점 인지, 불 필요한 범위를 넘는지, 방문했었는지 확인 후 만족하는 정점만 큐에 넣는다.

#include <iostream>
#include <queue>
#include <stdlib.h>
#define P pair<int,int>
using namespace std;

queue<pair<int,int>> q;
int visit[140000];

void queuePush(int posi, int count) {
	if (posi >= 0 && posi <= 140000 && visit[posi] == 0) {
		P temp = make_pair(posi, count);
		q.push(temp);
		visit[posi] = 1;
	}
}

int main() {
	int n, k;
	cin >> n >> k;

	if (n == k) cout << "0";
	else {
		//시작 정점 넣기
		P p = make_pair(n, 0);
		q.push(p);
		visit[n] = 1;

		//큐에 넣고 빼기 반복
		while (!q.empty()) {
			p = q.front();
			q.pop();

			//목표인지 체크
			if (p.first * 2 == k || p.first + 1 == k || p.first - 1 == k) {
				cout << p.second + 1;
				break;
			}

			// 방문하거나 범위 넘는 자식 빼고 큐에 넣기
			queuePush(p.first * 2, p.second + 1);
			queuePush(p.first + 1, p.second + 1);
			queuePush(p.first - 1, p.second + 1);
		}
	}

	return 0;
}