1189 - 컴백홈

문제

코드

#include <bits/stdc++.h>
using namespace std;

int r,c,k;
char a[10][10];
int visited[10][10];
const int dy[4] = {-1,0,1,0};
const int dx[4] = {0,1,0,-1};

int check(int y, int x){
	if(y == 0 && x == c-1){
		if(visited[y][x] == k)return 1;
		return 0;
	}
	int ret = 0;
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny < 0 || ny >= r || nx >=c || nx < 0 || visited[ny][nx] || a[ny][nx] == 'T') continue;
		visited[ny][nx] = visited[y][x] + 1;
		ret += check(ny,nx);
		visited[ny][nx] = 0;	
	}
	return ret;
}

int main(){
	cin >> r >> c >> k;
	for(int i = 0; i <r; i++){
		for(int j = 0; j < c; j++){
			cin >> a[i][j];
		}
	}
	
	visited[r-1][0] = 1;
	cout << check(r-1, 0);
}

풀이

결과

후기

탐색 알고리즘을 생각해 내는게 굉장히 까다로웠다.
한번에 쭉 나가는 탐색을 생각하기보다 모두 가는데 한줄씩 나가는 그런 재귀를 생각해 내는 것이 조금 힘들었다.
그리고 아무리 해도 재귀는 너무 헷갈린다.
return이 3개나 있는데 언제 어디로 가고 이게 왜 이건지 짜는 순간 적어놓고 나중에 보면 굉장히 헷갈린다...
재귀는 좀 맡기자... 놓자... 컴퓨터가 해주겠지...