[알고리즘 문제] 71. 송아지 찾기(BFS : 상태트리탐색)

코드

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

using namespace std;

int ch[10001], d[3] = { -1, 1, 5 };

int main(void)
{
	int s, e, x, pos, i;
	cin >> 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 <= 0 || pos > 10000) continue;
			if (pos == e)
			{
				// 출발 지점을 1로 잡았기 때문에 이전 지점 출력
				cout << ch[x] << endl;
				return 0;
			}
			if (ch[pos] == 0)
			{
				ch[pos] = ch[x] + 1;
				Q.push(pos);
			}
		}
	}

	return 0;
}

 

출력 결과

 

채점 결과

 

 

해당 포스트는 'it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비' 강의를 수강하며 개인 백업용으로 메모하였습니다.

인프런: https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#

it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 - 인프런