송아지 찾기(BFS, 상태트리탐색)/ c & c++ / 제한시간 없음

▣ 입력설명

- 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아 지의 위치가 직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.

현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성 하세요.

 

▣ 입력설명

- 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000 까지이다.

 

▣ 출력설명

- 점프의 최소횟수를 구한다.

 

▣ 입력 에시

5 14

 

▣ 출력 예시

3

 

<코드> - c++

#pragma warning(disable:4996)
#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

int visit[10000];
int dx[3] = { 1,-1,5 };

int main() {
	int s, e, i, pos, x;
	queue<int> Q;
	scanf("%d %d", &s, &e);
	visit[s] = 1;
	Q.push(s);
	while (!Q.empty()) {
		x = Q.front();
		Q.pop();
		for (i = 0; i < 3; i++) {
			pos = x + dx[i];
			if (pos <= 0 || pos >= 10000) continue;
			if (pos == e) {
				printf("%d\n", visit[x]);
				exit(0);
			}
			if (visit[pos] == 0) {
				visit[pos] = visit[x] + 1;
				Q.push(pos);
			}
		}
	}
	return 0;
}

코드의 기본적인 구조는 시작 위치에서 dx[ ]를 통해 이동할 수 있는 위치들을 큐(Queue)에 넣는다. dequeue를 하면서 현재 위치가 'e'와 같으면 프로그램을 종료한다.

 

이 코드에서 중요한 부분은 visit[ ]이다. 이전과 다르게 단순히 방문 유무만 표시하는게 아니라 점프의 최소 횟수도 같이 저장해준다. 

 

visit[pos] = visit[x] + 1;

이 라인이 점프의 최소 횟수를 표현하는 식이다. 입력 예시를 예로 들면 '5'에서 시작해서 처음에 갈 수 있는 위치들은 '6' '4' '10' 이 된다. 그러면 visit[6], visit[4], visit[10]에는 움직이기 전의 위치인 'visit[5] = 1' 보다 1을 더해준다것을 의미한다.

 

이처럼 처음 시작 부분인 'visit[s]=1'로 해주었기 때문에 답을 출력할때는 움직이기 전의 위치인 visit[x]를 출력해준다. 

 

<코드> - c

#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>

int main() {
	int visit[10000] = { 0 }, dx[3] = { 1,-1,5 };
	int s, e, pos, i, x;
	int queue[1000];
	int front = 0, rear = 0;
	scanf("%d %d", &s, &e);
	visit[s] = 1;
	queue[rear++] = s;
	while (front < rear) {
		x = queue[front++];
		for (i = 0; i < 3; i++) {
			pos = x + dx[i];
			if (pos <= 0 || pos >= 10000) continue;
			if (pos == e) {
				printf("%d\n", visit[x]);
				exit(0);
			}
			if (visit[pos] == 0) {
				visit[pos] = visit[x] + 1;
				queue[rear++] = pos;
			}
		}
	}
	return 0;
}

위와 같은 방법으로 c언어로 짠 코드이다.