백준 13565 c++

재귀는 아직도 익숙해지질 않는다...
알고리즘 자체는 처음부터 맞았지만 복귀했을 경우에 방문기록을 초기화 한것이 문제였다. 좀더 고민해봐야 겠다.

#include <iostream>
#include <vector>

using namespace std;

int M, N;
vector <vector<int>> graph;
vector <vector<bool>> visited;
vector <pair<int, int>> direction{ {0, 1}, {1, 0}, {-1, 0}, {0, -1} };
bool success = false;

void input_graph()
{
	int i, j;
	string str;
	
	cin >> M >> N;
	graph.resize(M, vector<int>(N, 0));
	visited.resize(M, vector<bool>(N, false));
	for (i = 0; i < M; i++)
	{
		cin >> str;
		for (j = 0; j < N; j++)
		{
			graph[i][j] = str[j] - '0';
		}
	}

	/*for (i = 0; i < M; i++)
	{
		for (j = 0; j < N; j++)
		{
			cout << graph[i][j] << " ";
		}
		cout << "\n";
	}*/

	return;
}

void DFS(int start_x, int start_y)
{
	int next_x, next_y;
	int i;
	
	//cout << start_x << " " << start_y << "\n";
	if (start_y == M - 1 || success)
	{
		success = true;
		return;
	}
	for (i = 0; i < direction.size(); i++)
	{
		next_x = start_x + direction[i].first;
		next_y = start_y + direction[i].second;
		if ((next_x >= 0 && next_x < N) && (next_y >= 0 && next_y < M) 
			&& graph[next_y][next_x] == 0
			&& visited[next_y][next_x] == false)
		{
			visited[next_y][next_x] = true;
			DFS(next_x, next_y);
		}
		if (success)
		{
			return;
		}
	}
}

void find_answer()
{
	//통하는지 확인하는 용도이므로 DFS로 푼다.
	int i, j;

	for (i = 0; i < N; i++)
	{
		if (graph[0][i] == 0)
		{
			visited[0][i] = true;
			DFS(i, 0);
			//visited[0][i] = false;
		}
		if (success)
		{
			break;
		}
	}
	if (success)
	{
		cout << "YES\n";
	}
	else
	{
		cout << "NO\n";
	}

	return;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	input_graph();
	find_answer();

	return 0;
}