[BaekJoon] 백준 1697번 숨바꼭질

 

[BaekJoon] 백준 1697번 숨바꼭질

 

 

문제: https://www.acmicpc.net/problem/1697

 

 

내코드

 

 

- bfs문제인데 인접한 값 == 수빈이가 이동할 수 있는 위치(즉, 수빈이의 현재 위치를 x라고 하면 x-1, x+1, x*2)으로 생각하고 풀면 간단한 문제.

- 처음에 런타임 에러가 나서 왜 그런가 봤더니 수빈이가 이동하는 위치가 100,000을 넘어가면 visited에서 배열의 범위가 초과되기 때문에 나는 거였다.

- 그리고 틀렸다고 나와서 이번에는 수빈이와 동생의 위치가 같을 때를 따로 조건을 걸어주었다.

- 배열을 초기화 할때 bool visited = { false, }이런식으로 하니까 전체가 같은 값으로 초기화가 됨.

- 아래는 아이패드에 정리한 내용.

 

백준 1697번 숨바꼭질.pdf

2.24MB

#include <iostream>
#include <stdio.h>
#include <string>
#include <queue>
#include <utility>

using namespace std;

int n, k;
queue<pair<int, int>> qu;
bool visited[100001] = { false, };
pair<int, int> current;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> k;
	if (n == k) {
		cout << 0;
		return 0;
	}
	qu.push(make_pair(n, 0));
	visited[n] = true;

	while (!qu.empty()) {
		current = qu.front();
		qu.pop();
		int x = current.first;
		int y = current.second;
		if (x-1 >= 0 && visited[x - 1] == false) {
			if ((x - 1) == k) {
				cout << y + 1;
				return 0;
			}
			qu.push(make_pair(x - 1, y + 1));
			visited[x - 1] = true;
		}
		if (x+1 <= 100000 && visited[x + 1] == false) {
			if ((x + 1) == k) {
				cout << y + 1;
				return 0;
			}
			qu.push(make_pair(x + 1, y + 1));
			visited[x + 1] = true;
		}
		if (x*2 <= 100000 && visited[x * 2] == false) {
			if ((x * 2) == k) {
				cout << y + 1;
				return 0;
			}
			qu.push(make_pair(x * 2, y + 1));
			visited[x * 2] = true;
		}
	}
	return 0;
}

 

참고