[BOJ 백준] 1697번 : 숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

숨바꼭질 시리즈를 전부 풀어보려고 한다.

 

총 6개의 숨바꼭질 문제가 있으며, 내용은 거의 똑같지만 문제가 요구하는 조건이 조금씩 다르다. 

 

대부분 탐색문제이며 BFS, DFS, 다익스트라를 잘 활용해서 풀면 될 듯 하다.

 

 

동생의 위치를 찾을 수 있는 가장 빠른 시간을 구하는 것이므로 BFS를 활용해서 풀 수 있다. 기본적인 BFS를 구현하면 되는 간단한 문제였다.

 

 

문제 해결 

• 큐에 해당 위치와 해당 위치에 도착한 시간을 저장하고, 방문 여부를 visit 배열을 통해 체크한다.
• BFS탐색을 하며 앞, 뒤, 순간이동을 했을 때의 정보를 큐와 visit 배열에 저장한다.
• 방문 하는 위치가 k(동생의 위치)와 같으면 탐색을 종료한다.

 

 

소스코드

#include<iostream>
#include<queue>
#include<string.h>
#define MAX 100001
using namespace std;
int n, k;
bool visit[MAX];
int time

int bfs(int n, int k) {
	queue<pair<int, int>>q; // 위치, 시간 저장
	q.push({ n, 0 });
	visit[n] = true;

	while (!q.empty())
	{
		int pos = q.front().first;
		int time = q.front().second;
		q.pop();

		if (pos == k)
			return time;

		if (pos + 1 < MAX && !visit[pos + 1]) {
			q.push({ pos + 1, time + 1 });
			visit[pos + 1] = true;
		}
		if (pos - 1 >=0 && !visit[pos - 1]) {
			q.push({ pos - 1, time + 1 });
			visit[pos - 1] = true;
		}
		if (pos * 2 < MAX && !visit[pos * 2]) {
			q.push({ pos *2, time + 1 });
			visit[pos*2] = true;
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);	cout.tie();
	//freopen("input.txt", "r", stdin);
	cin >> n >> k;
	cout<<bfs(n, k);
}