백준 12851 [C++]

www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

1. 풀이방법 

 

- 숨바꼭질 4를 풀었다고 만만하게 덤볐다가 큰 코 다친 문제입니다..

 

- 문제를 많이 풀다보면 코드를 짤때 그 의미를 생각하지않고 항상 짜던데로 습관적으로 짜는 경향이 있는데,,,,

 

- 50퍼 정도에서 틀렸습니다 가 계속 나와서 질문검색에서 도움을 받았습니다.

 

-www.acmicpc.net/board/view/22749

글 읽기 - 12851번 숨바꼭질2 오답이 될만한 입력값

- 이분의 글을 보고 도움을 받았습니다.

 

- 제가 틀린 부분을 찾은 예시는

 

- 1 4

  입력시

  2

  2

(저는 1이 나왔었습니다)

- 였습니다.

 

-  1 -> 1+1 -> (1+1) * 2 (여기서 만약 2를 체크하면)

   1 -> 1*2 -> (1*2) * 2 (이 예시가 케이스로 들어가지 않음)

 

- 그래서 이 문제에서는 BFS를 돌때 큐에 넣을 때 VISIT을 체크하는 것이 아니라 큐에서 뺄 때 VISIT을 체크했습니다.

 

- 그외에는 K를 발견하면 그때의 큐를 끝까지 다 보는 방식으로 구현했습니다.

 

 

 

2. 주의사항

 

- 의미를 항상 생각하며 코드를 짜자!

 

 

 

3. 나의코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int n, k;
int resultcount;
bool visit[100001];
queue<int> tmpq;
vector<int> tmpv;
int second = 1;
int nextn;
int qsize;
bool suc = false;
void checkrest() {
	while (qsize--) {
		nextn = tmpq.front(); tmpq.pop();
		if (nextn + 1 <= 100000 && nextn + 1 == k) resultcount++;
		if (nextn - 1 >= 0 && nextn - 1 == k) resultcount++;
		if (nextn * 2 <= 100000 && nextn * 2 == k) resultcount++;
	}
}

void bfs() {	
	while (1) {
		tmpv.clear();
		qsize = tmpq.size();
		while (qsize--) {
			nextn = tmpq.front();
			tmpq.pop();
			visit[nextn] = true;
			tmpv.push_back(nextn);
			
			//1증가
			if (nextn + 1 <= 100000 && visit[nextn + 1] == false) {
				tmpq.push(nextn + 1);
				if (nextn+1 == k) {
					resultcount++;
					checkrest();
					return; }
			}

			if (nextn - 1 >= 0 && visit[nextn - 1] == false) {
				tmpq.push(nextn - 1);
				if (nextn-1 == k) {
					resultcount++;
					checkrest();
					return; }
			}

			if (nextn * 2 <= 100000 && visit[2 * nextn] == false) {
				tmpq.push(nextn * 2);
				if (nextn*2 == k) {
					resultcount++;
					checkrest();
					return; }
			}
		}
		second++;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> k;
	if (n >= k) {
		cout << n - k << "\n";
		cout << 1 << " ";
	}
	else {
		tmpq.push(n);
		visit[n] = true;
		bfs();
		cout << second << "\n" << resultcount << "\n";
	}
	return 0;
}