백준 12851 - 숨바꼭질 2(C++)

문제 링크입니다. https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

BFS를 이용한 문제였습니다.

방문한 곳을 체크할 때, 위치를 다르게 해야지 풀리는 문제입니다.

N부터 K까지 최소 거리 및 최소로 올수 있는 경우의 수를 모두 구하는 문제입니다.

다른 문제와 같이 방문함과 동시에 check 배열의 값을 바꾸어주면 정확한 값이 나오지 않습니다.

 

이런 경우에는 queue에서 현재 좌표를 pop을 한 뒤, check 배열을 바꾸어주면 됩니다.

(check 배열의 경우 이전에 방문했는지의 여부를 저장하는 배열입니다.)

 

문제를 풀 때 주의할 점이 있습니다.

1. 수빈이가 이동할 수 있는 좌표는 0 ~ 100,000입니다. 따라서 해당 좌표 안에서 움직일 수 있도록 해야합니다.

2. 경우의 수를 세줄때, 저장된 최소 거리보다 작은 값이 있으면, 수를 1로 초기화를 해줘야합니다. 같을 경우에만 증가시킵시다.

3. 기존에 저장된 최소 거리보다 큰 값이 들어온다면, 저장된 queue를 통해 갈 수 있는 거리는 모두 최소 거리가 아니라는 의미입니다.

    그러니 break를 해주면 시간과 메모리를 줄일 수 있습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#define Max 100001

using namespace std;

int N, K;
int check[100001];
int ans = 100001;
int way;

void bfs(){
	queue<pair<int,int>> q;
	q.push(make_pair(N,0));
	check[N] = 1;
	while(!q.empty()){
		int x = q.front().first;
		int cnt = q.front().second;
		q.pop();
		check[x] = 1;
		if(x == K){
			if(ans > cnt){
				ans = cnt;
				way = 1;
			}
			else if(ans == cnt) way++;
			else break;
		}
		else{
			if(x + 1 >= 0 && x + 1 < Max){
				if(check[x + 1] == 0){
					q.push(make_pair(x + 1,cnt+1));
				}
			}
			if(x - 1 >= 0){
				if(check[x - 1] == 0){
					q.push(make_pair(x - 1,cnt+1));
				}
			}
			if(x * 2 > 0 && x * 2 <= Max){
				if(check[x * 2] == 0){
					q.push(make_pair(x * 2,cnt+1));
				}
			}
		}
	}
}

void solve(){
	bfs();
	cout << ans << "\n" << way;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> K;
	solve();	
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!