BOJ - 1189번 컴백홈 (C++)

문제 출처: https://www.acmicpc.net/problem/1189

문제 난이도

Silver 1

문제 접근법

처음엔 K길이의 가짓수래서 Bfs와 count 배열을 두고 접근했다. 그러나 bfs는 한 층? 한 정점이 사방으로 이어진 정점으로 이어진 한 너비를 보기 때문에 해당 좌표가 겹치면 count가 다시 갱신된다는 것을 알았다.
그래서 dfs를 이용해서 풀었다. 이게 훨씬 생각하기 쉽다.

통과 코드

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

#define INF 987654321

using namespace std;

bool ch[6][6];
int dy[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int R, C, K;
char arr[6][6];

int dfs(int x, int y, int cnt) {
	if (cnt == K) {
		return arr[x][y] == 'H' ? 1 : 0;
	}
	
	int ret = 0;
	for (int k = 0; k < 4; k++) {
		int nx = x + dy[k][0];
		int ny = y + dy[k][1];
		if (nx < 0 || ny < 0 || nx >= R || ny >= C || arr[nx][ny] == 'T' || ch[nx][ny]) continue;
		ch[nx][ny] = true;
        	ret += dfs(nx, ny, cnt + 1);
        	ch[nx][ny] = false;
	}
	
	return ret;
}

int main() {
	
	cin >> R >> C >> K;
	
	for (int i = 0; i < R; i++) {
		for(int j=0; j<C; j++){
        	    cin >> arr[i][j];
        	}
	}
    
    	ch[R-1][0] = true;
	arr[0][C - 1] = 'H';
    
	int res = dfs(R - 1, 0, 1);
	cout << res << "\n";
    
	return 0;
}

피드백

home 좌표를 H 라고 임의로 값을 지정했다. 처음엔 걍 좌표 오른쪽 위면 return하게 했지만 다른 사람 코드를 참고하니 이렇게 푸는게 더 직관적이고 코드를 이해할 때 쉬워서 나도 이렇게 수정하게 됐다!