[BOJ 백준] 12851번 : 숨바꼭질2

www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

숨바꼭질2는 1과 달리, 최단 시간으로 동생을 찾는 경우의 수까지 출력하는 문제이다.

 

경우의 수를 따로 체크하는 것을 제외하면 숨바꼭질 1 의 풀이와 똑같다.

 

문제해결

• 동생을 찾은 시간의 값을 저장하는 배열(answer)을 만든다.
  • 최대로 걸리는 시간은 수빈이가 0에 있고, 동생이 100000에 위치하고 있을 때 1칸 씩 앞으로 가면 100000초가 걸리는 것이므로 배열의 최대 크기는 100000이면 된다.
• 동생을 찾았을 때의 시간인 answer[time]의 값을 1 증가한다.
• 가장 빠른 시간을 구하기 위해 answer 배열의 0번째 인덱스부터 확인해가며 0이 아닌 값이 나올 경우 출력하고, 그대로 종료한다.

소스코드

#include<bits/stdc++.h>
#define endl "\n"
#define MAX 100000+1
using namespace std;
int arr[MAX];
int answer[MAX]; // n초에 찾는 경우의 수
int moving[3] = { -1,1,0 }; // 뒤로가기, 앞으로가기, 순간이동
int n, k;

void bfs() {
	queue<pair<int, int>>q;
	q.push({ n,0 }); // 현재 위치, 시간
	arr[n] = 0;
	while (!q.empty()) {
		int cur_pos = q.front().first;
		int cur_time = q.front().second;
		q.pop();
		arr[cur_pos] = cur_time;
		if (cur_pos == k) { 
			answer[cur_time]+=1;
		}
		moving[2] = cur_pos; // 순간이동
		for (int i = 0; i < 3; i++) {
			int next_pos = cur_pos + moving[i];			
			int next_time = cur_time + 1;
			if (next_pos<0 || next_pos>MAX)continue; // 동생에게 도달 할 수 있는 범위 초과
			if (arr[next_pos] == 0) {
				q.push({ next_pos, next_time });
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("input.txt", "r", stdin);
	cin >> n >> k;
	bfs();
	for (int i = 0; i < MAX; i++) {
		if (answer[i] != 0) { // 가장 빠른 시간을 출력
			cout << i << endl;
			cout << answer[i];
			return 0;
		}
	}
}