DFS & BFS - 백준 1697번 숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

IDEA

아 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

최근에 본 네이버부캠 코테에서 같은 유형의 문제가 나왔었는데,,,,,ㅜㅜ 못풀었다. 생소한 느낌이라서 

DFS나 BFS로는 맨날 2차원좌표만 접하다보니까 2차가 아닐때의 BFS나 DFS가 생소했었나보다,,,,,

익숙해질겸 이후 비슷한 문제를 추천받아 백준 5014번 스타트링크 (www.acmicpc.net/problem/5014) 연습했다.

 

이 문제에서는 수빈이가 동생의 위치로 갈 수 있는 최단시간을 물어보고 있다.

최단시간 -> BFS를 이용했다. 

 

현재 수빈이 위치가 X라면 3가지 방향으로 움직일 수 있다. 

 

1. 한 칸 앞 : X + 1
2. 한 칸 뒤 : X - 1
3. 현재의 위치 두 배 앞 : 2X

새로나아갈 방향이 주어진 범위 내에 있으면서 방문을 하지 않았을 때, 그 위치로 이동할 수 있는 최단 거리를 VISITED에 저장해주었다. 

이미 방문처리되어있는 곳에 방문한다면 , 지금 경로는 최단이 아닐 것이다. 

이전 2차원 BFS를 풀 떄랑 똑같이 VISITIED[X+1] = VISITED[X] + 1 처럼 VISITED에 그 위치로 갈 수 있는 최단 거리를 저장해놨다.  

 

그 후 큐에서 꺼낸 위치가 목표랑 같다면 VISITED[위치] 를 반환해주었다. 

 

CODE

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

int visited[100001] = {0};
queue<int>q;
int start, target, answer = 1000001;

bool check(int n) {
	if (0 <= n && n <= 100001) return true;
	return false;
}

int bfs(int s) {
	q.push(s);
	while (!q.empty()) {
		int pos = q.front();
		//printf("현재 위치 : %d , visited 수 : %d\n", pos, visited[pos]);
		q.pop();
		if (pos == target)  return visited[pos];
		else {
			if (check(pos + 1) && !visited[pos + 1]) {
				visited[pos + 1] = visited[pos] + 1;
				q.push(pos + 1);
			}
			if (check(pos - 1) && !visited[pos - 1]) {
				visited[pos - 1] = visited[pos] + 1;
				q.push(pos - 1);
			}
			if (check(2 * pos) && !visited[2 * pos]) {
				visited[2 * pos] = visited[pos] + 1;
				q.push(pos *2);
				}
			}
	}
}

int main() {
	scanf("%d %d", &start, &target);
	printf("%d", bfs(start));
}