[BOJ] 17071 숨박꼭질5

 

https://www.acmicpc.net/problem/17071

17071번: 숨바꼭질 5

BFS 를 통해 해결하였습니다.

각 좌표에 대해 가장 먼저 도착하는 시간을 저장시켰습니다.

도착이후 2의 배수번을 더하면(+1 이후 -1) 다시 제자리로 돌아올 수 있기 때문에 시간을

홀수 짝수로만 나누어 저장하였고 이후 동생을 이동시키며 동생이 지나가는 좌표값에 수빈이가 처음 도착하는 시간이   

더 빠를 경우에 min값을 업데이트 시켰습니다.

 

#include<iostream>
#include<queue>
#include<vector>
#include<map>
#pragma warning (disable:4996)
using namespace std;
// 17071 숨박꼭질5
int line[500100][2];
bool avail(int i) {
	if (i >= 0 && i <= 500000)
		return true;
	return false;
}
int main(){
	for (int i = 0; i < 500001;i++) {
		line[i][0] = -1;
		line[i][1] = -1;
	}
	int n, k;
	cin >> n >> k;
	int j = 0;
	if (n == k) {
		cout << 0 << endl;
		return 0;
	}
	queue<int>q;
	q.push(n);
	line[n][0] = 0;
	int cnt = 1;
	while (!q.empty()) {
		int len = q.size();
		//cout << cnt<<" "<<len << endl;
		while (len--) {
			int num = q.front(); q.pop();
			if (avail(num - 1) && line[num - 1][cnt % 2]==-1) {
				q.push(num - 1);
				line[num - 1][cnt % 2] = cnt;
			}
			if (avail(num + 1) && line[num + 1][cnt % 2]==-1) {
				q.push(num + 1);
				line[num + 1][cnt % 2] = cnt;
			}
			if (avail(num *2) && line[num * 2][cnt % 2]==-1) {
				q.push(num *2);
				line[num * 2][cnt % 2] = cnt;
			}
		}
		cnt++;
	}
	j = 0;
	int mmin = 5000000;

	for (; k <=500000;k+=++j) {
		if (j>=line[k][j%2]&&mmin>j) {
			mmin = j;
		}
	}
	cout << (mmin == 5000000 ? -1 : mmin);

}

 

#잡설

88% 지점에서 계속 틀렸습니다가 나와서 어디가 틀렸지 한참을 찾았습니다.

초반부분에 q에 입력된 n값을 넣을때 line[n][0] 만 0으로 초기화가 되어야 하는데

line[n][1]도 초기화를 해서 발생한 오류였습니다.

이전 코드에서 500000 499999에서 틀린결과가 출력되었습니다.