백준 1189 c++

간단한 DFS문제인데 BFS나 DP로 풀어보려고 하다가 오히려 시간만 버렸다.
시작점과 끝점이 평소 풀던 문제와 달라서 입력할때 반대로 입력하게 했다.
그리고 DFS에서도 visited를 적극 사용해야 겠다.

#include <iostream>
#include <vector>

using namespace std;

vector<vector<char>> map;
vector <vector<bool>> visited;
vector<pair<int, int>>direction{ {1, 0}, {0, 1}, {-1, 0},  {0, -1} };
int R, C, K;//R이 y, C가 x
int answer = 0;

void input_map()
{
	int i, j;

	cin >> R >> C >> K;
	map.resize(R, vector<char>(C));
	visited.resize(R, vector<bool>(C, false));
	for (i = R-1; i >= 0; i--)
	{
		for (j = 0; j < C; j++)
		{
			cin >> map[i][j];
		}
	}
	/*for (i = 0; i < R; i++)
	{
		for (j = 0; j < C; j++)
		{
			cout << map[i][j] << " ";
		}
		cout << "\n";
	}*/

	return;
}

void DFS(int x, int y, int count)
{
	int i;
	int next_x, next_y;
	//cout << "현위치 x = " << x << ", y = " << y << ", count = " << count << "\n";

	if (count == K && (x == C-1 && y == R-1))
	{
		answer++;
		return;
	}
	for (i = 0; i < 4; i++)
	{
		next_x = x + direction[i].first;
		next_y = y + direction[i].second;
		if ((next_x >= 0 && next_x < C) && (next_y >= 0 && next_y < R))
		{
			if (map[next_y][next_x] == 'T' || visited[next_y][next_x] == true)
			{
				continue;
			}
			if (map[next_y][next_x] == '.')
			{
				visited[next_y][next_x] = true;
				DFS(next_x, next_y, count + 1);
				visited[next_y][next_x] = false;
			}
		}
	}
}

void find_answer()
{
	int start_x = 0, start_y = 0;

	//cout << "DFS시작" << "\n";
	visited[start_y][start_x] = true;
	DFS(start_x, start_y, 1);
	cout << answer << "\n";

	return;
}

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

	input_map();
	find_answer();

	return 0;
}