[백준] 2665번. 미로만들기 (C++)

문제

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

 

주의 사항

메모리초과가 났다. 그래서 vector를 배열로 바꿨다.

 

해결

BFS로 풀었다.

visit 초기값을 아주 큰 수로 두고

visit에 이 길까지 오는데 검정방을 몇번 들렸는지 저장 (count) 했다.

새로운 count가 visit count값 보다 작은 경우에만 탐색하게 했다.

 

검정방일 경우에 visit에 +1을 하고

흰색 방이면 그대로 넣어준다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int m[101][101];
int visit[101][101];

int dirX[] = { -1,1,0,0 };
int dirY[] = { 0,0,-1,1 };

int main()
{
	int N;
	cin >> N;

	//MAP INPUT
	for (int i = 0; i < N; ++i) 
	{
		string line; cin >> line;
		for (int j = 0; j < N; ++j) 
		{
			m[i][j] = line[j] - '0';
			visit[i][j] = 2147483647;
		}
	}
	
	//FIRST
	queue<tuple<int, int>> q;
	q.push({ 0, 0});
	visit[0][0] = 0;

	//BFS
	while (!q.empty())
	{
		int nowX = get<0>(q.front());
		int nowY = get<1>(q.front());
		int nowCount =visit[nowY][nowX];

		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nextX = nowX + dirX[i];
			int nextY = nowY + dirY[i];

			if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) continue;


			if (m[nextY][nextX] == 1 && visit[nextY][nextX] > nowCount)//white Room
			{
				visit[nextY][nextX] = nowCount;
				q.push({ nextX,nextY});
			}
			else if(visit[nextY][nextX] > nowCount +1)//black Room
			{
				visit[nextY][nextX] = nowCount + 1;
				q.push({ nextX,nextY});
			}
		}
	}

	cout << visit[N - 1][N - 1];
	return 0;
}