[백준/BOJ] 백준 16930번 : 달리기

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

16930번: 달리기

 

bfs(너비 우선 탐색)을 이용하는데, 움직이려는 방향의 k개만큼 모두 이동하는 게 아닌, 움직이려는 방향으로 1~k 칸을 확인해 나아가다가, 만약 확인하는 위치가 이전에 이미 현재 이동하는 것보다 더 빠른 길로 도착한 경우, 그쪽 방향의 확인은 이전에 도착한 경우에 맡기면 되기 때문에, 그쪽 방향은 더 이상 확인하지 않는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;

int n, m, k;
vector<string> board;
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
pair<int, int> start, dest;

int solve() {
	vector<vector<int>> discovered(1005, vector<int>(1005, -1));
	queue<pair<int, int>> q;
	discovered[start.first][start.second] = 0;
	q.push(start);

	while (!q.empty()) {
		pair<int, int> here = q.front();
		q.pop();

		if (here.first == dest.first && here.second == dest.second) {
			return discovered[here.first][here.second];
		}

		for (int dir = 0; dir < 4; dir++) {
			for (int i = 1; i <= k; i++) {
				pair<int, int> there = make_pair(here.first + (dxdy[dir][0] * i), here.second + (dxdy[dir][1] * i));

				//구간을 벗어나지 않을때
				if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m) {

					if (board[there.first][there.second] == '#') { //there가 벽일때
						break;
					}

					//there가 지금 가려는것 보다, 이전에 이미 더 빠른 길로 도착한 경우일때
					//i번째 이후 부터 k까지 더 보는것은 여기서 할 필요가 없이, 이전에 이미 더 빠른 길로 도착한 경우 쪽에 맡기면 된다
					if (discovered[there.first][there.second] != -1 && discovered[there.first][there.second] < (discovered[here.first][here.second] + 1)) {
						break;
					}

					if (discovered[there.first][there.second] == -1) {
						discovered[there.first][there.second] = discovered[here.first][here.second] + 1;
						q.push(there);
					}
				}
			}
		}
	}

	return -1;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++) {
		string row;
		cin >> row;
		board.push_back(row);
	}

	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	start = make_pair(x1 - 1, y1 - 1);
	dest = make_pair(x2 - 1, y2 - 1);

	int result = solve();
	cout << result;

	return 0;
}