[c++] 송아지 찾기, 공주구하기(queue)

송아지 찾기

내가짠 코드

#include <iostream>
#include <vector>
#include <queue>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int ch[10000], dis[10000];
int val[] = {1, -1, 5};
int main() {
	//freopen("input.txt", "rt", stdin);
	int n, m, i, a, b, x, res, min=2147000000;
	vector<int> map[10000];
	queue<int> Q;
	scanf("%d %d", &n, &m);
	Q.push(n);
	ch[n]=1;
	while(!Q.empty()){
		x=Q.front();
		Q.pop();
		for(i=0; i<3; i++){
			map[x].push_back(x+val[i]);
			if(ch[map[x][i]]==0){
				ch[map[x][i]]=1;
				Q.push(map[x][i]);
				dis[map[x][i]]=dis[x]+1;
			}
			if(map[x][i]==m){
				res=dis[map[x][i]];
				printf("%d\n", res);
				exit(0);
			}
		}
	}
	return 0;
}

 

강의코드

#include <iostream>
#include <vector>
#include <queue>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int ch[10000], dis[10000];
int val[] = {1, -1, 5};
int main() {
	//freopen("input.txt", "rt", stdin);
	int n, m, i, a, b, x, pos;
	queue<int> Q;
	scanf("%d %d", &n, &m);
	Q.push(n);
	ch[n]=1;
	while(!Q.empty()){
		x=Q.front();
		Q.pop();
		for(i=0; i<3; i++){
			pos=x+val[i];
			if(pos==m){
				printf("%d\n", ch[x]);
				exit(0);
			}
			if(ch[pos]==0){
				ch[pos]=ch[x]+1;
				Q.push(pos);
			}
		}
	}
	return 0;
}

트리를 탐색할 때에는 이중배열을 사용해서 연관관계를 무조건 지어야 한다고 생각해서(왜그런생각밖에 들지않았는지는 모르겠지만) map 이중배열로 선언했다.

그런데 이중배열로 받지 않아도 되었다. 

첫번째 값을 알면 1, -1, 5를 각각 더해서 다음 숫자를 만들 수 있으니 만들어진 숫자가 방문되지 않은 숫자라면

다음 숫자를 큐에 넣고 체크배열에 1을 더해주면 해당 숫자까지 가는데 점프한 횟수를 구할 수 있다.

 

 

 

공주구하기

#include <iostream>
#include <vector>
#include <queue>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int ch[1000];
int main() {
	//freopen("input.txt", "rt", stdin);
	int n, m, i, a, b, x, pos;
	queue<int> Q;
	scanf("%d %d", &n, &m);
	for(i=1; i<=n; i++){
		Q.push(i);
	}
	ch[n]=1;
	i=0;
	while(!Q.empty()){
		i++;
		x=Q.front();
		Q.pop();		
		if(i==m) i=0;
		else Q.push(x);
	}
	printf("%d", x);
	return 0;
}