[백준]Baekjoon1697(DFS,BFS,백트래킹,Dynamic Programming)

문제링크 : https://www.acmicpc.net/problem/1697

풀이

문제 분류가 DFS, BFS로 되어있고 실제로 정답을 맞춘 사람들의 풀이를 보면 큐를 이용해서

푼 사람들이 대부분이지만 난 그냥 Dynamic Programming 으로 풀었다.

Dynamic Programming으로 푼다고하면 아마 초기값 설정에서 애매하게 느낄 수 있겠지만

난 그냥 수빈이 위치 이전값들은 걸어서 이동하는 것 밖에 방법이 없으므로 

수빈이 위치를 0으로 놓은 상태에서 1씩 증가시키면서

일일히 다 넣어주었다.

그런다음 수빈이 위치 + 1 부터 동생의 위치 + 1까지 for문을 통해 반복문을 진행하면서

만약 인덱스 i가 짝수라면 다음과 같이

arr[i] = min(arr[i / 2] + 1, arr[i - 1] + 1); 

수빈이가 i/2에서 순간이동 할 수 있으므로 그 때 걸린 시간과 , 걸었을 떄 걸린시간을 비교해서 

배열에 넣어주었고 

만약 동생의 위치가 17일 때 16에서 17로 걸어서 이동한것보다 9에서 18로 순간이동 후 걸어서

이동한게 더 시간이 적게 걸릴 수 있으므로 이를 반영하여

if (i != 0) arr[i - 1] = min(arr[i - 1], arr[i] + 1);

이렇게 다시 또 조건문을 수행할 수 있도록 하였다.

코드는 다음과 같다.

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100001];
int main()
{
	int N, K;
	scanf("%d %d", &N, &K);
	arr[N] = 0;
	int num = 1;
	for (int i = N - 1; i >= 0; i--) arr[i] = num++;

	if (K > N) {
		for (int i = N + 1; i <= K+1; i++) {
			if (i % 2 == 0) {
				arr[i] = min(arr[i / 2] + 1, arr[i - 1] + 1);
			}
			else
				arr[i] = arr[i - 1] + 1;
			if (i != 0) arr[i - 1] = min(arr[i - 1], arr[i] + 1);
		}
	}
	printf("%d\n", arr[K]);
}

이와 별도로 BFS를 통해 푼 풀이를 같이 첨부하면서 풀이를 마치겠다.

#include <iostream>
#include <queue>

using namespace std;

bool check[100001];

int main()
{
	int N, K;
	scanf("%d %d", &N, &K);
	int time = 0;
	queue<pair<int, int>> q;
	q.push(make_pair(N, time));
	int index;

	while (1)
	{
		index = q.front().first;
		time = q.front().second;
		q.pop();

		check[index] = true;
		if (index == K) {
			printf("%d\n", time);
			break;
		}
		time++;

		int nx[3] = { index + 1,index - 1,index * 2 };
		for (int i = 0; i < 3; i++) {
			if (nx[i] > 100000 || nx[i] < 0) continue;
			if (check[nx[i]]) continue;
			q.push(make_pair(nx[i], time));
		}
	}

}