취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13700번 문제인 완전 범죄이다.
문제는 아래 링크를 확인하자.

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

문제의 주어진 상황은 각 건물 i를 노드로 생각하고, i번 노드에서 i+F번 노드로, i번 노드에서 i-B번 노드로 향하는 방향간선이 있는 방향그래프로 모델링할 수 있다. 단, i번째 건물이 경찰서인 경우 없는 노드 취급하고, 범위를 벗어난(i+F>N 또는 i-B<1) 노드로 이동하는 에지 또한 없는 에지 취급하자.

위 방향그래프의 S번 노드에서 D번 노드까지의 최단거리를 BFS를 이용해 구하는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

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

int N, S, D, F, B, K;

int dist[100001];

void bfs() {
	dist[S] = 1;
	queue<int> que;
	que.push(S);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		if (cur + F <= N && dist[cur + F] == 0) {
			dist[cur + F] = dist[cur] + 1;
			que.push(cur + F);
		}
		if (cur - B > 0 && dist[cur - B] == 0) {
			dist[cur - B] = dist[cur] + 1;
			que.push(cur - B);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> S >> D >> F >> B >> K;
	while (K--) {
		int x; cin >> x;
		dist[x] = -1;
	}

	bfs();

	if (dist[D] == 0) cout << "BUG FOUND";
	else cout << dist[D] - 1;
}