백준 1697 숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

BFS를 이용해서 풀었는데 자꾸 틀렸습니다가 뜸

 

시작점(N)에 다시 방문하지 않게 하기 위해 visited[N]을 1로 넣고 시작했더니 [1 1] 같은 케이스에서 0이 아닌 2가 출력된 것이었음.

bfs 앞부분에 같으면 0 출력하고 종료하는 코드를 넣으니까 풀렸다.

visited랑 몇번째 방문인지 체크하는 배열을 따로 선언해야 하나 고민중

 

 사실 visited가 0이 아니면 무조건 방문한 거니까 거기에 몇번째 방문인지 체크하는게 메모리 효율은 좋을텐데, 고려해야 할 사항이 늘어나서 번거롭기도 하다.

 

 

#include<iostream>
#include<queue>
using namespace std;
int n, k;

int visited[200001];

void bfs() {
	if (n == k) {
		cout << 0 << endl;
		return;
	}
	queue<int> q;
	q.push(n);
	visited[n] = 1;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		if ((cur + 1) == k || (cur - 1) == k || (cur * 2) == k) {
			cout << visited[cur] << endl;
			return;
		}
		if ((cur + 1) <200000 && visited[cur + 1] == 0) {
			q.push(cur + 1);
			visited[cur + 1] = visited[cur] + 1;
		}
		if ((cur + 1) >= 0 && visited[cur - 1] == 0) {
			q.push(cur - 1);
			visited[cur - 1] = visited[cur] + 1;
		}
		if ((cur * 2) < 200000 && visited[cur * 2] == 0) {
			q.push(cur * 2);
			visited[cur * 2] = visited[cur] + 1;
		}
	}
}

int main() {
	cin >> n >> k;
	bfs();
	return 0;
}