백준 16930 - 달리기

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

16930번: 달리기

풀이

---

푸는데 좀 많이 애먹은 문제였다.

계속해서 96% 부분에서 시간초과가 나서 고민 했는데 결국 찾긴 찾았다.

 

이 문제는 BFS로 풀었다.

한 노드를 탐색하고 K 만큼 주변 노드들을 탐색한다.

해당 노드가 방문된 횟수가 현재 방문 횟수보다 크거나 같다면 탐색을 계속하고 작으면 다른 방향으로 탐색을 시작한다.

방문한 노드가 처음 방문한 노드라면 큐에 담고 아니라면 방문횟수를 업데이트하고(안해도 정답이 나온다) 다음 노드 탐색을 한다.

 

코드

---

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <math.h>
using namespace std;
char map[1003][1003];
int flag[1003][1003] = { 0 };
int X, Y, K;
int startX, startY, endX, endY;

int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };
bool InMap(int x, int y) {
	if (0 <= x && x < X && 0 <= y && y < Y)
		return true;
	return false;
}

void BFS(int x,int y) {
	queue<pair<int, int>> queue;
	queue.push(make_pair(x, y));
	int count = 0;
	flag[y][x] = 0;
	while (!queue.empty()) {
		int queueX = queue.front().first;
		int queueY = queue.front().second;
		count = flag[queueY][queueX] + 1;
		queue.pop();
		for (int k = 0; k < 4; k++) {
			for (int i = 1; i <= K; i++) {
				int surroundX = queueX + dx[k] * i;
				int surroundY = queueY + dy[k] * i;
				if (InMap(surroundX, surroundY) && map[surroundY][surroundX] == '.' && flag[surroundY][surroundX] >= count) {
					if (flag[surroundY][surroundX] == 10000000) {
						queue.push(make_pair(surroundX, surroundY));
						flag[surroundY][surroundX] = count;
						if (surroundY == endY && surroundX == endX) {
							cout << count << endl;
							return;
						}
					}
					flag[surroundY][surroundX] = count;
				}
				else {
					break;
				}
			}
		}
	}
	cout << -1 << endl;
}

int main() {
	cin >> Y >> X >> K;

	for (int y = 0; y < Y; y++) {
		string key;
		cin >> key;
		for (int x = 0; x < X; x++) {
			flag[y][x] = 10000000;
			map[y][x] = key[x];
		}
	}
	cin >> startY >> startX >> endY >> endX;
	startX--;
	startY--;
	endX--;
	endY--;
	BFS(startX, startY);
	return 0;
}