백준 13549. 숨바꼭질 3

알고리즘 기초 문제 중 610 - BFS

숨바꼭질 3

1. 간단 설명

숨바꼭질 시리즈 중 3번째 문제

기존 문제와 차이점은 순간이동시 시간이 소요되지 않는다는 점이다

걷는건 1초를 소모하지만 순간이동은 0초다

이를 고려하여 풀면 됨

2. 예시

• 예제 1)

5 17

5 10 9 18 17 -> 2초

• 예제 2)

1 2

0초 (순간이동 한번)

• 예제 3)

5 1 동생이 수빈이보다 앞쪽 좌표에 있음

4초 (X-1 4번)

3. 알고리즘

필요 변수

• 수빈이와 동생의 좌표 int N, K (0 ≤ N, K ≤ 100,000)
• 좌표와 시간을 기록할 struct node{int pos; int sec;}
• 해당 좌표를 방문한 적이 있는지 기록할 int visited[100001] <- 10만도 포함해야함
• BFS 탐색용 큐

알고리즘

1. 수빈이와 동생의 좌표를 입력받는다
2. 큐에 수빈이의 좌표와 초기 시간값 0을 넣는다
3. BFS 시작
	3-1. 큐에서 맨 앞 노드를 꺼냄
	3-2. 이 노드의 좌표값을 동생과 비교
		- 동생과 일치하다면 이 노드의 시간 출력 후 종료
	3-3. 순간이동, X-1, X+1 를 각각 시도해봄
		3-3-1. 만약 다음 이동할 좌표가 경계 밖이라면 패스
		3-3-2. 만약 다음 이동할 좌표가 이미 방문한적 있다면 패스
		3-3-3. 다음 노드를 방문처리 후
			3-3-3-1. 순간이동이라면 초를 증가시키지 않고 다음 좌표와 현재 노드의 시간을 큐에 맨뒤에 넣는다
			3-3-3-2. 걷는 경우라면, 큐의 맨 뒤에 다음 좌표와 현재 노드 +1초를 넣는다 

주의사항

• 0 100000 과 같이 0과 10만도 범위에 포함되므로 주의
• 어떤 이동을 먼저 시도할것인지 주의

4. 소스코드

#include <iostream>
#include <queue>

using namespace std;

struct node {
	int pos;
	int sec;
};

int N, K;
int visited[100001];

int main() {
	cin >> N >> K;
	
	queue<node> qu;
	qu.push({ N, 0 }); 
	visited[N] = 1;

	while (!qu.empty()) {
		node now = qu.front();
		qu.pop();

		if (now.pos == K) {
			cout << now.sec;
			return 0;
		}

		int direct[3] = { now.pos, -1, 1 }; // now.pos+now.pos = 2 * now.pos

		// 순간이동을 먼저 시도

		for (int t = 0; t < 3; t++) {
			int next = now.pos + direct[t];
			if (next < 0 || next > 100000) continue; // 경계 체크
			if (visited[next] == 1) continue; // 방문체크

			visited[next] = 1;
			if (t == 0) { // 순간이동은 시간을 소모하지 않음
				qu.push({ next, now.sec});
			}
			else { 
				qu.push({ next, now.sec + 1});
			}
			
		}
	}

	return 0;
}

다음 이동위치를 체크할 때 int direct[3] = {-1, 1, now.pos};를 사용했으나 오답이 출력되었다

이 문제에서는 순간이동이 시간을 소모하지 않으므로, 순간이동을 우선하여 시도해야한다

즉 위에 direct 배열은 걷는걸 우선했기 때문에 선입선출을 갖는 큐의 특성상 오답이 출력된 것

BFS 탐색 시, 다음 위치를 어느쪽을 먼저 시도하느냐에 따라 성능이 달라지므로 주의할 것!!