[Softeer/C++] 나무 섭지

https://softeer.ai/practice/7726

Softeer - 현대자동차그룹 SW인재확보플랫폼

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Pos {
	int y, x;
	Pos() : y(0), x(0) {}
	Pos(int y, int x) : y(y), x(x) {}
};

int n, m;

string board[1004][1004];
int visitNamwoo[1004][1004];
int visitGost[1004][1004];
Pos exitPos;

queue<Pos>namwooQ;
queue<Pos>goastQ;

int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };


void GoastBFS()
{
	while (goastQ.empty() == false)
	{
		Pos now = goastQ.front();
		goastQ.pop();

		for (int i = 0; i < 4; i++)
		{
			int nextY = now.y + dy[i];
			int nextX = now.x + dx[i];

			if (nextY < 0 or nextY >= n or nextX < 0 or nextX >= m)
				continue;

			if (visitGost[nextY][nextX] != 0)
				continue;

		/*	visitGost[nextY][nextX] = visitGost[now.y][now.x] + 1;
			goastQ.push(Pos(nextY, nextX));*/

			if (visitGost[nextY][nextX] == 0)
			{
				visitGost[nextY][nextX] = visitGost[now.y][now.x] + 1;
				goastQ.push(Pos(nextY, nextX));
			}
		}
	}
}

void NamWooBFS()
{
	while (namwooQ.empty() == false)
	{
		Pos now = namwooQ.front();
		namwooQ.pop();

		for (int i = 0; i < 4; i++)
		{
			int nextY = now.y + dy[i];
			int nextX = now.x + dx[i];

			if (nextY < 0 or nextY >= n or nextX < 0 or nextX >= m)
				continue;

			if (board[nextY][nextX] == "#" || visitNamwoo[nextY][nextX] != 0)
				continue;

			//유령이 도착할 수 없는 곳 이거나 유령의 거리보다 남우의 거리가 작을 때
			if (visitGost[nextY][nextX] == 0 ||  visitNamwoo[now.y][now.x] + 1 < visitGost[nextY][nextX]) {
				visitNamwoo[nextY][nextX] = visitNamwoo[now.y][now.x] + 1;
				namwooQ.push(Pos(nextY, nextX));
			}
		}
	}
}

int main() {

	cin >> n >> m;

	string in;
	for (int y = 0; y < n; y++)
	{
		cin >> in;
		string s = in;

		for (int x = 0; x < m; x++)
		{
			board[y][x] = s[x];

			if (s[x] == 'N')
			{
				namwooQ.push(Pos(y, x));
				visitNamwoo[y][x] = 1;
			}
			else if (s[x] == 'D')
			{
				exitPos = Pos(y, x);
			}
			else if (s[x] == 'G')
			{
				goastQ.push(Pos(y, x));
				visitGost[y][x] = 1;
			}
		}
	}

	//n = 4; m = 6;
	//// 주어진 보드 설정 (보드의 크기는 문제에 따라 조정해야 함)
	//board[0][0] = "."; board[0][1] = "."; board[0][2] = "."; board[0][3] = "#"; board[0][4] = "."; board[0][5] = "D";
	//board[1][0] = "."; board[1][1] = "."; board[1][2] = "."; board[1][3] = "#"; board[1][4] = "."; board[1][5] = ".";
	//board[2][0] = "."; board[2][1] = "G"; board[2][2] = "N"; board[2][3] = "#"; board[2][4] = "."; board[2][5] = ".";
	//board[3][0] = "G"; board[3][1] = "."; board[3][2] = "."; board[3][3] = "."; board[3][4] = "."; board[3][5] = ".";
	//for (int y = 0; y < n; y++) { // 보드 높이에 맞게 수정 (여기서는 4줄만 출력)
	//	for (int x = 0; x < m; x++) { // 보드 너비에 맞게 수정

	//		string s = board[y][x];
	//		board[y][x] = s;

	//		if (s == "N")
	//		{
	//			namwooQ.push(Pos(y, x));
	//			visitNamwoo[y][x] = 1;
	//		}
	//		else if (s == "D")
	//		{
	//			exitPos = Pos(y, x);
	//		}
	//		else if (s == "G")
	//		{
	//			goastQ.push(Pos(y, x));
	//			visitGost[y][x] = 1;
	//		}
	//	}
	//	cout << endl;
	//}

	GoastBFS();
	NamWooBFS();

	if (visitNamwoo[exitPos.y][exitPos.x] == 0)
		cout << "No";
	else
		cout << "Yes";

	return 0;
}