[백준] 온라인 저지 2178번 : 미로 탐색(C++), DFS

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

#include <iostream>
#include <vector>
#include <string>

using namespace std;

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

void dfs(vector<vector<int>>& Maze, vector<vector<bool>>& Visited, int y, int x, int count, int& answer)
{
	Visited[y][x] = true;
	if (y == N - 1 && x == M - 1)
	{
		if (count < answer || answer== -1)
			answer = count;
	}
	
	for (int i = 0; i < 4; ++i)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];

		if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;

		if (Maze[ny][nx] == 1 && Visited[ny][nx] == false)
		{
			dfs(Maze, Visited, ny, nx, count + 1, answer);
		}
	}
	Visited[y][x] = false;
}


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

	vector<vector<int>> Maze(N, vector<int>(M));
	vector<vector<bool>> Visited(N, vector<bool>(M, false));
	char Input;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			cin >> Input;
			if (Input == '1') Maze[i][j] = 1;
			else Maze[i][j] = 0;
		}
	}

	int answer = -1;
	dfs(Maze, Visited, 0, 0, 1, answer);
	cout << answer << endl;
}

DFS는 시간초과 발생 BFS로 다시 풀어보기