백준 - 14497번 : 주난의 난(難) (C++)

풀이 방법 : 다익스트라

문제를 보고 처음엔 뭔 소린가 싶었다. 밑에 있는 힌트 정보를 보고 난 뒤에야 문제를 이해했다.

결국에는 그래프 탐색을 진행해가면서 사람을 가장 적게 만나면서 범인에게 도달하는 경우를 찾는 문제였다.

그래서 구조체에 좌표정보와 파동이 거쳐간 사람의 수를 저장하여 우선순위 큐에 저장하여 거쳐간 사람의 수가 더 적은 파동 정보부터 검토하도록 구현해서 풀었다.

#include <iostream>
#include <queue>

using namespace std;

char Room[301][301] = {};
bool check[301][301] = {};
int DirX[4] = { 1,-1,0,0 };
int DirY[4] = { 0,0,1,-1 };

struct Wave
{
	int Cnt = 1;
	int PosY = 0;
	int PosX = 0;
};

struct cmp
{
	bool operator() (const Wave& A, const Wave& B)
	{
		return A.Cnt > B.Cnt;
	}
};

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, M;
	cin >> N >> M;

	int x1, y1, x2, y2;
	cin >> y1 >> x1 >> y2 >> x2;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			cin >> Room[i][j];
		}
	}

	priority_queue<Wave, vector<Wave>, cmp> pqWave;

	Wave Start;
	Start.PosY = y1 - 1;
	Start.PosX = x1 - 1;
	pqWave.push(Start);
	check[Start.PosY][Start.PosX] = true;

	int Min = N * M + 1;

	while (!pqWave.empty())
	{
		Wave Cur = pqWave.top();
		pqWave.pop();

		for (int i = 0; i < 4; ++i)
		{
			Wave Next = Cur;

			Next.PosY += DirY[i];
			Next.PosX += DirX[i];

			if (Next.PosY < 0 || Next.PosY >= N ||
				Next.PosX < 0 || Next.PosX >= M)
				continue;

			if (check[Next.PosY][Next.PosX])
				continue;

			check[Next.PosY][Next.PosX] = true;

			if (Room[Next.PosY][Next.PosX] == '1')
				++Next.Cnt;

			else if (Room[Next.PosY][Next.PosX] == '#')
			{
				cout << Next.Cnt;
				return 0;
			}

			pqWave.push(Next);
			
		}

	}

	cout << Min;

}