Baekjoon/cpp

1697번 - 숨바꼭질 C++

_yh47 2023. 7. 9. 01:16

 

문제 설명


그래프 탐색 문제

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

 

1697번: 숨바꼭질

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

 

 

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

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

 

5에서 17을 잡을 때

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

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

 

 

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


https://yhoons.tistory.com/4

 

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

다익스트라 알고리즘이란? 더보기 : 그래프에서 엣지(노드) 간에 최단 거리(가중치 합 최소)를 구하는 알고리즘 그래프 알고리즘 문제에도 많이 쓰이는 알고리즘 중에 하나이며, 실생활에선 네

yhoons.tistory.com


코드

#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;
	
}
반응형