1697번 - 숨바꼭질 C++

 

문제 설명

---

그래프 탐색 문제

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

1697번: 숨바꼭질

 

 

BFS와 dijkstra 알고리즘을 섞어 사용했습니다.

문제 예시로 나와있듯이 수빈이가 -1, +1, *2 칸을 이동해서 동생을 잡는 건데요.

 

5에서 17을 잡을 때

5 -> 4 -> 8 -> 16 -> 17 처럼 최소 시간으로 잡아야합니다.

그러기 위해선 최단 경로 알고리즘인 다익스트라 알고리즘을 이용합니다.

 

 

다익스트라 알고리즘이란?

---

https://yhoons.tistory.com/4

다익스트라 알고리즘(Dijkstra algorithm) - c++

---

코드

#include<iostream>
#include<queue>

std::queue<int> q; //수빈이의 최단 경로 위한 큐
const int INF = 10000000;
int N, K;
int arr[100001] = {0,};


int hideandseek (int N)
{
	arr[N] = 0; //시작지점이므로 거리는 0
	q.push(N); //큐에 넣음으로써 인접 칸(-1, +1, *2) 확인
    
	while(!q.empty())
	{
		N = q.front(); //while문 안에서 큐원소가 pop,push되므로 업데이트
	    q.pop();
		int move[] = {-1, 1, N}; //칸 이동 표현, N은 *2와 같음 N*2 = N+N		
		for(int i=0; i<3; i++)
		{
			int next_n = move[i] + N; //다음 탐색할 칸을 변수 next_n에 저장
			if(next_n < 0 || next_n > 100000)
			    continue;
	    	if(arr[N] + 1 < arr[next_n]) //저장되어 있는 값보다 작다면 그 값이 최단거리
			{
				arr[next_n] = arr[N] + 1;
				q.push(next_n);
			}
		}

	}
	return arr[K];
}


int main()
{
	std::cin >> N >> K;
	
	for(int i=0; i<=100000; i++)
	{
		arr[i] = INF;
	}
	
	std::cout << hideandseek(N) << std::endl;
	
}