백준 13700 - 완전 범죄(C++)

문제 링크입니다. https://www.acmicpc.net/problem/13700

13700번: 완전 범죄

BFS를 이용해 푸는 문제였습니다.

금은방의 위치 S에서 시작해 집의 위치인 D로 가려고 할 때, 최소 몇 번만에 갈 수 있는지를 구하는 문제입니다.
한번에 앞으로 갈 수 있는 수는 F, 뒤로 갈 수 있는 수는 B입니다.
F, B를 이용해, 경찰서를 피하면서 도착하면 됩니다.

경찰서의 위치는 주어지기 때문에, 배열을 이용해 경찰서 위치의 값을 1로 변경합니다.
그렇다면 배열의 값이 0이라면 갈 수 있는곳, 1이라면 갈 수 없는 곳이 됩니다.

위치 S에서 BFS 탐색을 시작해주면 됩니다. 갈 수 있는 곳은 X+F, X-B입니다.
이동한 위치가 1 이상 N 이하이며, 해당 위치의 배열의 값이 0이여야 하고, 이전에 방문하지 않은 곳이라면
-> 해당 위치로 이동한 뒤, 이동 변수를 하나 증가해줍니다.

해당 과정을 queue가 빌 때 까지 반복하며, queue가 비었지만 도착하지 못했다면, “BUG FOUND”, 도착했다면 도착 변수 값을 출력해주면 됩니다.



자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N, S, D, F, B, K;
int map[100001];
int check[100001];

int bfs(){
	queue<pair<int, int>> q;
	q.push({S, 0});
	check[S] = 1;
	while(!q.empty()){
		int x = q.front().first;
		int cnt = q.front().second;
		q.pop();
		if(x == D) return cnt;
		int x_1 = x + F;
		int x_2 = x - B;
		if(x_1 >= 1 && x_1 <= N){
			if(map[x_1] == 0 && check[x_1] == 0){
				check[x_1] = 1;
				q.push({x_1, cnt + 1});
			}
		}
		if(x_2 >= 1 && x_2 <= N){
			if(map[x_2] == 0 && check[x_2] == 0){
				check[x_2] = 1;
				q.push({x_2, cnt + 1});
			}
		}
	}
	
	return 0;
}

void solve(){
	int ans = bfs();
	if(ans == 0) cout << "BUG FOUND";
	else cout << ans; 
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> S >> D >> F >> B >> K;
	for(int i = 1; i <= K; i++){
		int x;
		cin >> x;
		map[x] = 1;
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.