[BOJ] 1697 - Catch That Cow

안녕하세요.

여행벌입니다.

오늘은 BFS 문제인 BOJ 1697 문제를 다뤄보겠습니다.

---

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

[알고리즘설계]

가능한 모든 경우를 BFS 탐색을 하며, 각 경우에 대해서 현재까지 몇 번 움직였는지 Count를 세줍니다.

가장 먼저 도착지점(End)에 도달하면, Count를 출력하며 종료합니다.

 

-주의사항

1.모든 경우에 대해서 움직이기 전에 가능한 index인지 체크해줘야 됩니다.

2.이미 와본 지점에 대해서는 더 진행할 필요가 없습니다.(이미 그전에 진행했으니까 Count가 클 수밖에 없음.)

#include<iostream>
#include<queue>

using namespace std;

void BFS(int, int);
bool check[100001];

int main(void) {
	int start, end;
	cin >> start >> end;
	BFS(start, end);
	return 0;
}

void BFS(int start, int end) {
	queue<int> q;
	queue<int> count;
	q.push(start);
	count.push(0);
	while (!q.empty()) {
		int x = q.front();
		int c = count.front();
		q.pop();
		count.pop();

		if (x == end) {
			cout << c;
			return;
		}
		if (x + 1 <= 100000 && !check[x+1]){
            check[x+1] = true;
			q.push(x + 1);
			count.push(c + 1);
		}
		if (2 * x <= 100000 && !check[2 * x]) {
            check[2*x] = true;
			q.push(2 * x);
			count.push(c + 1);
		}
		if (0 <= x-1 && !check[x-1]){
            check[x-1] = true;
			q.push(x - 1);
			count.push(c + 1);
		}
	}
}

---

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.

혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.

많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 

감사합니다.