문제 링크

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

사용 언어

C++14

소스

#include <iostream>
#include <queue>
using namespace std;
  
int N, S, D, F, B, K;
int count[100000];
bool visited[100000];
queue<int> q;
  
int main()
{
	cin >> N >> S >> D >> F >> B >> K;
	visited[S-1] = true;
	int pos;
	for(int i = 0; i < K; i++){
		cin >> pos;
		visited[pos-1] = true;
	}	
  	
	q.push(S-1);
	while(!q.empty()){
		pos = q.front();
		q.pop();
  
		int nextF = pos+F;
		int nextB = pos-B;
		if(pos == D-1){
			cout << count[pos];
			return 0;
		}
		if(nextF < N && !visited[nextF]){
			visited[nextF] = true;
			count[nextF] = count[pos]+1;
			q.push(nextF);
		}
		if(nextB >= 0 && !visited[nextB]){
			visited[nextB] = true;
			count[nextB] = count[pos]+1;
			q.push(nextB);
		}
	}
	cout << "BUG FOUND";
}

논리

1회차에 앞으로 갈 수도 있고, 뒤로 갈 수도 있다.

또한 2회차에도 해당 자리에서 앞으로 갈 수도 있고, 뒤로 갈 수도 있다.

여기서 주목할 포인트는 한 번 방문한 건물은 다시 방문할 필요가 없다는 점이다.

정말 그러할까? 한 번 증명을 해보도록 하겠다.

• def

  경로 C = c₁c₂…c_k (각 i 에 대해, c_i+1 = c_i + F 또는 c_i - B을 만족)

• claim

  최소경로 C에는 두 개 이상의 같은 건물을 포함하지 않는다.

• proof

  귀류법을 통해 증명하도록 하자. 따라서 다음과 같이 결론을 부정해본다.

  “서로 다른 어떤 i, j 가 존재하여 c_i = c_j 이다.”

  먼저 일반성을 잃지 않고 i < j 라고 둘 수 있다.

  그러면 c_j = c_i = c_i-1 + F 또는 c_i-1 - B 이므로 C’ = c₁c₂ … c_i-1c_j … c_k 는 경로이다.

  특히, 도착점에 도달하는 C보다 더 짧은 경로임을 알 수 있다.

  이것은 C가 최소 경로라는 가정에 모순이다.

  따라서 최소경로 C에는 두 개 이상의 같은 건물을 포함하지 않는다.

  
  

방문한 곳을 다시 조사할 필요가 없다면 많아봐야 N번의 조사를 통해 최소경로를 찾을 수 있다.

방문한 곳 뿐만 아니라 방문할 수 없는 곳을 visited배열에 true값을 넣음으로써,

방문할 필요가 없도록 한다.

즉, police의 위치도 visited에 true값으로 넣음으로써 코드를 단순화 하였다.