[알골90제] 71번 - 송아지 찾기 (BFS: 상태트리탐색)

* 문제

최소 몇번의 점프로 현재 위치 S에서 송아지 위치 E까지 갈 수 있는지

- 직선의 좌표점은 1부터 10000까지

- 한번의 점프로 앞으로 1 뒤로 1 앞으로 5까지 갈 수 있다.

 

ex. 현재 위치 5에서 송아지 위치 14까지는 3번만에 갈 수 있다.

10 15 14

 

+5 +5 -1

 

어떤 정점에서 어떤 정점까지 최단거리!를 구하여라 이런 것은 BFS 사용

 

 

 

* 상태트리 만들기

 

1. 5를 만들고 5에서 한번만에 갈 수 있는 것 다 트리로 만들기

 

5에서 한번만에 갈 수 있는 지점

 

2. 각 트리에서 또 2번만에 갈 수 있는 지점 만들기

이미 큐에 들어간 자료 ex.5는 체크를 걸어서 다시는 큐에 들어가지 않게 체크를 해버린다.

 

각 정점에서 갈 수 있는 정점 구함. 중복되는 정점은 체크배열로 따로 체크해두어 저장하지 않는다

 

큐에 넣어가며, 상태트리를 만들며

1번 만에 가는 것 보기 

2번 만에 가는 것 보기

3번 만에 가는 것 보기

.

.

레벨 탐색을 통해 최단 거리 구하기!

 

 

// 71번 - 송아지 찾기 BFS: 상태트리탐색

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

//d[3] 방향 배열: 이동하며 더해가며 좌표값 구함
int ch[10001], d[3] = { 1, -1, 5 };

int main() {

	int s, e, x, pos;  //x:큐에서 이용, pos: 현재위치
	scanf("%d %d", &s, &e);

	queue<int> Q;
	ch[s] = 1;
	Q.push(s);

	while (!Q.empty()) {
		x = Q.front();
		Q.pop();
		for (int i = 0; i < 3; i++) {
			pos = x + d[i];
			if (pos < 1 || pos > 10000) continue;
			if (pos == e) {
				printf("%d\n", ch[x]);
				exit(0);
			}
			if (ch[pos] == 0) {
				ch[pos] = ch[x] + 1; //ch배열은 거리배열도 됨
				Q.push(pos);					//ch[x]는 s에서 x까지 가는 최소 점프횟수가 들어가있음
			}
		}

	}

	return 0;
}