백준 BOJ 1697 - 숨바꼭질

나름 괜찮다고 생각한 문제

너무 직설적이지 않으면서도 어떤 알고리즘을 써야 풀리는지가 명확해 좋았다.

 

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

#include <stdio.h>
#include <queue>
#include <string.h>
#include <utility>

using namespace std;

queue<pair<int,int>> q;
int n,k;
int sec=1;
int visit[123456] = {0};

bool border(int pos){
	if(0 <= pos && pos <= 100000) return true;
	else return false;
}

int bfs(){
	while(!q.empty()){
		int fir = q.front().first;
		int sec = q.front().second;
		q.pop();
		
		if(fir == k) return sec;
		
		visit[fir] = 1;		
		if(border(fir+1) && visit[fir+1] != 1) q.push({fir+1, sec+1});
		if(border(fir-1) && visit[fir-1] != 1) q.push({fir-1, sec+1});
		if(border(fir*2) && visit[fir*2] != 1) q.push({fir*2, sec+1});
	}
}

int main(){
	scanf("%d %d", &n, &k);
	q.push({n,0});
	printf("%d", bfs());
	return 0;
}

 

일단 bfs로 문제를 해결할수 있기에 큐를 만들어줬는데, 중요한점은 큐에 std::pair가 들어갔다는 점이다.

pair의 용도는 후에 나오게 된다.

visit배열 또한 만들고,

 

border함수는 세그폴트가 일어나지 않게 해주는 함수이다.

if문에 &&과 함께 넣으면 C언어의 구조적 특징 때문에

border함수가 0을 반환시 뒤의 문장을 무시해서 세그폴트가 발생하지 않는다.

 

bfs함수에선 while문으로 모든 숫자를 탐색하게 되는데,

fir변수는 현재 위치한 장소의 좌표고

sec변수는 현재 몇걸음을 걸었는지를 저장해두었다.

만약 현재의 장소가 찾아야하는 위치와 같다면 바로 반환해주면서 반복문을 빠져나오게 되고,

그렇지 않을경우 이 장소를 방문했다는 표시를 남기고 탐색을 진행한다.

세그폴트가 일어나지 않으면서 방문하지 않은 위치들을 방문해주면,

bfs의 특성상 가까운순서부터 탐색하게 되기 때문에 굳이 값이 최소값인지 확인하는 과정을 거치지 않아도 된다.