[C++] 백준 13549번: 숨바꼭질 3

문제

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

 

 

13549번: 숨바꼭질 3

규칙에 따라 특정 위치로 이동하는 최단시간을 찾는 숨바꼭질 문제 시리즈입니다.

문제에서 시작지점에 위치한 수빈이는 1초의 시간을 소모하여 +1 또는 -1 로 움직이거나, 0초의 시간을 소모하여 현재 인덱스의 두 배 지점으로 순간이동을 할 수 있습니다.

 

이동 방식의 가중치가 다르기 때문에 다익스트라를 사용하셔도 되고, 이 문제의 경우 단순 bfs로 해결할 수도 있습니다.

다익스트라 풀이는 다른 블로그에도 많을 것이기 때문에 (정해이니까요) 제가 풀었던 단순 bfs 방법을 공유합니다.

 

사용 언어는 C++ 입니다.

 

코드

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

int n, k;
int visited[200000] = {0};
queue<pair<int, int>> q;

int bfs() {
	while(!q.empty()) {
		int value = q.front().first;
		int cnt = q.front().second;
		q.pop();
		
		if(value == k) return cnt;
		
		int teleport = 2;
		while(value*teleport < 200000 && visited[value*teleport] == 0) {
			q.push(make_pair(value*teleport, cnt));
			visited[value*teleport] = 1;
			teleport *= 2;
		}
		
		if(visited[value-1] == 0 && value-1 >= 0) {
			q.push(make_pair(value-1, cnt+1));
			visited[value-1] = 1;
		}
		
		if(visited[value+1] == 0 && value < 100000) {
			q.push(make_pair(value+1, cnt+1));
			visited[value+1] = 1;
		}
	}
}

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n >> k;
	
	q.push(make_pair(n, 0));
	visited[n] = 1;
	
	int res = (n==k) ? 0 : bfs();
	
	cout << res;
	return 0;
}

 

 

주의사항

이 풀이의 핵심은 bfs 내부의 반복문 구간입니다.

 

수빈이가 순간이동을 통해 이동할 수 있는 모든 경로를 체크해줘야 가장 먼저 나온 값을 최단 거리로 확정할 수 있기 때문에 반복문으로 미리 이동 가능한 경로를 모두 체크해줍니다. 이때 방문한 노드 확인은 반복문이 실행될때 해주는 것이 시간 단축에 도움이 됩니다. (실제로 반복문 내의 조건절에서 방문 노드를 확인하면 시간 초과를 받게 됩니다.)

 

한 가지 더 중요한 점은, 배열의 크기가 200000이기 때문에, 반복문 내부의 조건 순서가 바뀌게 되면 outOfBounds 오류를 받게되니 주의해야합니다. 위 코드에서는 value*teleport < 200000 를 먼저 판별해주게 되면 앞의 조건이 거짓일때 자동으로 뒤 조건은 검사하지 않는 특성을 이용해 추가적으로 조건을 설정해주진 않았습니다.

 

 

난이도가 있는 문제는 아니었지만, 개인적으로 bfs로 해결할 수 있는 문제는 bfs로 해결하는게 보기 깔끔하다고 생각해서 정리해보았습니다.