BOJ[1697] 숨바꼭질 C/C++

숨바꼭질

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <queue>

int check[1000000] = { 0, };

int main() {

	int n, m;
	scanf("%d %d", &n, &m);

	if (n == m) {
		printf("0");
	}
	else {
		std::queue<int> bfs;

		bfs.push(n);
		check[n] = 1;
		int count = 0;

		while (1) {
			count++;
			int size = bfs.size();
			int flag = 0;
			for (int i = 0; i < size; i++) {

				int p = bfs.front();
				bfs.pop();

				int a = p - 1;
				int b = p + 1;
				int c = p * 2;

				if (a == m || b == m || c == m) {
					flag = 1;
					break;
				}
				if (a >= 0 && a <= 100000) {
					if (check[a] == 0) {
						check[a] = 1;
						bfs.push(a);
					}
				}
				if (b >= 0 && b <= 100000) {
					if (check[b] == 0) {
						check[b] = 1;
						bfs.push(b);
					}
				}
				if (c >= 0 && c <= 100000) {
					if (check[c] == 0) {
						check[c] = 1;
						bfs.push(c);
					}
				}

			}
			if (flag == 1) {
				break;
			}
		}
		printf("%d", count);
	}
}​

넓이 우선 탐색(BFS)문제이다.

처음에 DP로 풀려 했지만 앞에서부터 이전 결과를 이용해 순차적으로 가는 것이 아니라서 만들다 실패했다.(앞,뒤로 가는 모든 경우가 있기 때문에)

BFS(넓이 우선 탐색)은 루트노드부터 시작해서 가장 가까운 노드들부터 탐색하는 알고리즘이다.

BFS는 재귀함수로 동작하지 않으며 이미 방문한 곳을 또 방문했을 시 무한루프에 빠질 수 있기 때문에 방문한곳은 다시 방문하지 않도록 체크해야 한다.

큐를 통해서 구현하였고 수진이와 뭐시기의 위치가 같을 때는 예외처리로 0이 출력되어야 한다.

또한 범위를 넘어서는 숫자들을 잘라주어야 한다.

C++에서 큐는 <queue>라이브러리를 사용해 추가할 수 있고 stack과 같은 함수들이 존재한다.