[백준/c++] 1697 - 숨바꼭질

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

1697번: 숨바꼭질

---

1) 풀이

이전에 풀이했던 BFS 문제들과는 다르게, 이번엔 일차원 배열에서 행해지는 bfs 문제이다.

어떻게 보면 이차원 배열보다 비교적 간단하다고 할 수 있다.

 

수빈이와 동생이 위치하고 있는 지점은 배열의 인덱스로 생각하면 된다.

숨바꼭질하는 판(board)과 수빈이가 동생을 찾는 시간을 저장하는 배열을 따로 둘 필요없이 

그냥 수빈이가 이동하는 좌표(인덱스)에 값으로 시간을 저장하면 된다.

 

board를 처음에 모두 -1로 초기화해두고 수빈이가 출발하는 지점 n 인덱스의 값은 0으로 지정해두고

수빈이가 위치를 옮길 때마다 이전 칸의 값에서 1을 더해주면, 수빈이가 그 칸에 방문했는지에 대한 여부도 

체크할 수 있다.

(수빈이가 칸을 옮길 때 모두 1초가 소요되므로 1을 더하는 것)

 

그렇게 수빈이가 칸을 옮길 때마다 그 칸에 도착했을 때 소요한 총 시간을 넣어주는 작업을 하다보면,

동생이 위치한 k칸에 도달했을 때, k 값도 기존에 초기화돼있던 -1에서 바뀌게 된다.

이것을 탐색 반복문의 종료조건으로 넣어주면, 수빈이가 동생을 찾았을 때 탐색이 바로 종료될 수 있다!!

이전과 같이 수빈이가 이동하는 좌표를 저장하는 queue 가 빌 때까지 를 조건으로 넣어버리면,

수빈이가 동생을 찾았음에도 이동을 멈추지 않아 최단 시간을 구하기 힘들어질 수 있다.

 

딱히 어려운 점은 없었던 문제!

 

2) 최종 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int board[100002]; 
int x[3] = { 1,-1,2 };
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, k;
	cin >> n >> k;

	fill(board, board + 100002, -1);

	queue<int>q; //수빈이가 이동하는 좌표 저장
	q.push(n);
	board[n] = 0; //수빈이가 출발하는 지점을 0
	while (board[k] == -1) { //k가 -1에서 바뀌는 순간 수빈이가 동생을 찾은 것
		int cur = q.front();
		q.pop();

		for (int i : {cur + 1, cur - 1, cur * 2}) {
			if (i < 0 || i>100000) continue; //범위 벗어남 
			if (board[i] >= 0) continue; //수빈이가 이미 지나간 곳
			q.push(i);
			board[i] = board[cur] + 1; //한칸 이동하는 데에 1초 걸리므로 이전칸보다 1더해주기
		}
	}
	cout << board[k];
}

3) 참고자료