문제

문제 링크

해설

• 좌표 (R-1, 0)에서 (0, C-1)로 cnt번 이동해서 가는 경우의 수를 구하는 문제입니다.
• DFS를 이용하면 쉽고 깔끔하게 풀 수 있습니다.

코드

#include <iostream>
using namespace std;

constexpr int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int R, C, K, answer;
char map[5][5];
bool visited[5][5];

void DFS(int y, int x, int cnt)
{
	if (cnt > K) return;
	if (cnt == K && y == 0 && x == C - 1) { answer++; return; }
	for (auto i : d) {
		int ny = y + i[0], nx = x + i[1];
		if (ny < 0 || nx < 0 || ny >= R || nx >= C || 
			map[ny][nx] == 'T' || visited[ny][nx]) continue;
		visited[ny][nx] = true;    // 방문표시
		DFS(ny, nx, cnt + 1);      // 방문표시 후 DFS 진행
		visited[ny][nx] = false;   // 방문표시 해제
	}
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> R >> C >> K;
	for (int y = 0; y < R; y++)
		for (int x = 0; x < C; x++)
			cin >> map[y][x];
	
	visited[R - 1][0] = true;
	DFS(R - 1, 0, 1);    // (R-1, 0) → (0, C-1) 이동
	cout << answer << '\n';
	return 0;
}

소스코드 링크

결과