🙇‍♀️송아지 찾기(BFS : 상태트리탐색)

현수는 송아지를 잃어버렸다.

다행히 송아지에는 위치추적기가 달려 있다.

현수의 위치와 송아지의 위치가 직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.

현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.

최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.

▣ 입력설명
첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 

직선의 좌표 점은 1부터 10,000까지이다.

▣ 출력설명
점프의 최소횟수를 구한다.

▣ 입력예제 1 
5 14

▣ 출력예제 1
3

🚀풀이

BFS문제이지만 먼저 DFS로 풀어봤다.

최소횟수는 S,E의 거리보다 작거나 같기 때문에 이것을 최대 조건으로 잡았다.

DFS 풀이법

void DFS(int here, int cnt)
{
	if (cnt > (abs(E - S) + 1))
		return;
	if (here == E)
	{
		res = min(cnt, res);
	}

	DFS(here + 1, cnt + 1);
	DFS(here - 1, cnt + 1);
	DFS(here + 5, cnt + 1);
}

이렇게 코드를 짜면 시간 초과가 나온다.

위 코드는 곂치는 부분이 너무 많다.

예를 들어
+1
+1 -1 +1
둘 다 같은 값이 지만 모두 계산한다.

아무튼 틀림.

시간 초과 날걸 알지만 한 이유! -> DFS연습

진짜 문제를 풀려면 BFS로 풀어야한다.

전의 최단거리랑 체크배열을 생각해서 아래와 같이 짰다.

BFS 풀이법

int dir[3] = { 1, -1, 5 };
void BFS(int pos)
{
	queue<int> q;
	pos = S;
	q.push(pos);

	while (q.empty() == false)
	{
		int pos = q.front();
		q.pop();

		for (int i = 0; i < 3; ++i)
		{
			int nPos = pos + dir[i];
			if (nPos <= 0 || nPos > 10000)
				continue;
			if (ch[nPos]) // 이미 도착했으면 넘김.
				continue;
			if (pos == E)
				return;

			q.push(nPos);
			ch[nPos] = ch[pos] + 1; // 최단 거리 구하기
		}
	}
}

위치 이동은 방향 배열을 만들어줘서 풀었다.

최단 거리 구하기가 왜 되나면 처음에 nPos를 만날 때가 최소 트리 레벨이기 때문이다.

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int S, E, res = 123456789;
int ch[10010];

// 최소값은 일단 E - S보다 작거나 같다.

void setting()
{
	cin >> S >> E;
}

void DFS(int here, int cnt)
{
	if (cnt > (abs(E - S) + 1))
		return;
	if (here == E)
	{
		res = min(cnt, res);
	}

	DFS(here + 1, cnt + 1);
	DFS(here - 1, cnt + 1);
	DFS(here + 5, cnt + 1);
}

int dir[3] = { 1, -1, 5 };
void BFS(int pos)
{
	queue<int> q;
	pos = S;
	q.push(pos);

	while (q.empty() == false)
	{
		int pos = q.front();
		q.pop();

		for (int i = 0; i < 3; ++i)
		{
			int nPos = pos + dir[i];
			if (nPos <= 0 || nPos > 10000)
				continue;
			if (ch[nPos])
				continue;
			if (pos == E)
				return;

			q.push(nPos);
			ch[nPos] = ch[pos] + 1;
		}
	}
}

void solve()
{
	setting();

	BFS(S);

	cout << ch[E];
}

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고