백준 - 2178 미로탐색

1. parent 방식을 이용할 수 있지만 반복문을 한 번 더 돌기 때문에 시간초과가 난다. 거리 계산 방식을 이용해야한다.

2. 방문을 다음 갈 곳을 찾았을때 바로 방문 했다고 알려줘야한다. 다음 이어지는 공간에서 중복되는 문제가 생긴다. 메모리 초과

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>

using namespace std;


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

struct Pos
{
	Pos(int X, int Y)
	{
		y = Y;
		x = X;
	}
	Pos() = default;

	int y;
	int x;

	bool operator<(const Pos& other) const
	{
		if (y != other.y)
			return y < other.y;
		return x < other.x;
	}

	bool operator!=(const Pos& other) const
	{
		if (y == other.y)
		{
			if (x == other.x)
			{
				return false;
			}
		}
		return true;
	}

	bool operator==(const Pos& other) const
	{
		return !(*this != other);
	}
};


int main(void)
{
	int N;
	int M;

	cin >> N >> M;

	int answer = 1;

	int arr[101][101];

	int dis[101][101];

	for (int i = 1; i <= N; ++i)
	{
		string str;
		cin >> str;
		for (int j = 1; j <= M; ++j)
		{
			arr[i][j] = str[j-1] - '0';
		}
	}

	//map<Pos, Pos> parent;

	Pos pos(1, 1);

	int g = N + 1;
	int h = M + 1;

	vector<vector<bool>> visited(g, vector<bool>(h, false));

	//parent[pos] = pos;

	dis[1][1] = 1;

	visited[pos.x][pos.y] = true;

	queue<Pos> q;
	q.push(pos);

	Pos dest(N, M);

	while (!q.empty())
	{
		pos = q.front();
		q.pop();

		if (pos == dest)
		{
			break;
		}


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

			
			if (x < 1 || x >= N + 1 || y < 1 || y >= M + 1)
			{
				continue;
			}

			if (visited[x][y] == true)
			{
				continue;
			}

			if (arr[x][y] == 0)
			{
				continue;
			}

			q.push(Pos(x, y));
			dis[x][y] = dis[pos.x][pos.y] + 1;
			visited[x][y] = true;

			//parent[Pos(x, y)] = pos;

		}
	}

	//pos = dest;
	//
	//while (true)
	//{
	//	if (parent[pos] == pos)
	//	{
	//		break;
	//	}
	//	pos = parent[pos];
	//	answer++;
	//}


	answer = dis[dest.x][dest.y];
	cout << answer;

	return 0;
}