백준 26009 험난한 등굣길

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

26009번: 험난한 등굣길

풀이 

0. 문제를풀기 앞서서 풀어야되는 문제

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

2178번: 미로 탐색

BFS를 이용해서 최단거리를 구해야됩니다. BFS를 공부합시다.

 

 

1. 핵심 아이디어

 

최단거리만 구한다면 단순한 BFS문제지만

해당 문제에서는 정체구역이라는 곳을 신경써야됩니다.

 

정체구역인 곳은 가지 못하므로 BFS로 탐색할때 지나갈수 없는곳으로 표시해야합니다.
BFS로 탐색하기전에 미리 전처리해서 표시합니다.

 

 

단 이문제에서 주의해야할 점이 있습니다.

 

N*M크기의 지도에 모든 정체구역을 모두 표시하려고하면

최악의 경우 (K*D*D = 3000*3000*3000)의 경우로 시간초과를 받게됩니다!!!

 

 

가만히 생각해보면 정체구역을 모두 표시할필요가 없습니다.
정체구역의 외각선만 표시하면됩니다!!

 

외각선만 표시한다고하면 (K*D*4 = 3000*3000*4)의 경우로 시간초과를 면할수 있습니다.

 

외각선만 정체구역으로 표시한후 BFS로 최단거리를 탐색하면 정답을 얻을 수 있습니다.

 

 

 

코드

#include <bits/stdc++.h>

#pragma warning(disable:4996)

using namespace std;

#define endl "\n"
#define int long long
#define float long double

const float INF = 1e10;
const int Dic[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

//////////////////////////////////////////////////////////////////////// 

int N, M, K;
bool Block[3005][3005];
bool IndexOut(int pR, int pC)
{
	return !(0 < pR && pR <= N && 0 < pC && pC <= M);
}
int Dist[3005][3005];

int32_t main()
{
	ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> N >> M;
	std::cin >> K;

	while (K--)
	{
		int R, C, D;
		std::cin >> R >> C >> D;

		//정체구역의 중심 표시
		Block[R][C] = true;

		//정체구역의 외각선을 표시
		for (int i = 0; i <= D; i++)
		{
			int aR = R - i * 1 + D;
			int aC = C + i * 1;
			if (IndexOut(aR, aC))
				continue;
			Block[aR][aC] = true;
		}
		for (int i = 0; i <= D; i++)
		{
			int aR = R - i * 1;
			int aC = C - i * 1 + D;
			if (IndexOut(aR, aC))
				continue;
			Block[aR][aC] = true;
		}
		for (int i = 0; i <= D; i++)
		{
			int aR = R + i * 1 - D;
			int aC = C - i * 1;
			if (IndexOut(aR, aC))
				continue;
			Block[aR][aC] = true;
		}
		for (int i = 0; i <= D; i++)
		{
			int aR = R + i * 1;
			int aC = C + i * 1 - D;
			if (IndexOut(aR, aC))
				continue;
			Block[aR][aC] = true;
		}
	}

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			Dist[i][j] = INF;

	queue<pair<int, int>> pq;
	pq.push({ 1,1 });
	Dist[1][1] = 0;

	while (pq.empty() == false)
	{
		pair<int, int> now = pq.front();
		pq.pop();

		int nowCost = Dist[now.first][now.second];

		for (int i = 0; i < 4; i++)
		{
			int nextCost = nowCost + 1;
			pair<int, int> next =
			{ now.first + Dic[i][0],now.second + Dic[i][1] };
			if (IndexOut(next.first, next.second))
			{
				//지역을 탈출했다.
				continue;		
			}
			if (Block[next.first][next.second])
			{
				//정체구역이므로 탐색 X
				continue;
			}
			if (Dist[next.first][next.second] != INF)
			{
				//이미 방문한 곳이다.
				continue;
			}

			Dist[next.first][next.second] = nextCost;
			pq.push(next);
		}
	}

	if (Dist[N][M] != INF)
	{
		std::cout << "YES" << endl;
		std::cout << Dist[N][M] << endl;
	}
	else
		std::cout << "NO" << endl;
}