백준 1189: 컴백홈

문제 요약

한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다.

R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

문제 분류

• 그래프 이론
• 브루트포스 알고리즘
• 그래프 탐색
• DFS
• 백트래킹

문제 풀이

x, y, fcnt값을 매개변수로 주고 cnt가 k보다 커질때 쳐내면 된다. k가 최단거리보다 커질 수 있으므로 상하좌우의 4방향을 전부 탐색해야 하며, 마지막 지점에 도착할 때에도 k와 fcnt의 값을 비교해야 한다.

visited배열로 탐색 여부를 보고, 시작점과 마지막점, fcnt의 초기값을 잘 설정해주면 쉽게 풀린다. 집으로 돌아갔을때 현재 fcnt의 값이 k와 맞는지 확인하고, 전역변수 cnt의 값을 1올려서 카운트 한다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

string ary[5];
bool visited[5][5];
int dir[4][2] = { {0,1},{-1,0},{1,0},{0,-1} };
int r, c, k, cnt = 0;

void dfs(int x, int y, int fcnt) {
	if (x == c - 1 && y == 0 && fcnt == k) {
		cnt++;
		return;
	}
	if (fcnt >= k) return;
	visited[y][x] = true;
	int ny, nx;
	for (int i = 0; i < 4; i++) {
		ny = y + dir[i][0];
		nx = x + dir[i][1];
		if (ny >= 0 && ny < r && nx >= 0 && nx < c) {
			if (!visited[ny][nx] && ary[ny][nx] != 'T') dfs(nx, ny, fcnt + 1);
		}
	}
	visited[y][x] = false;
}

int main()
{
	scanf("%d%d%d", &r, &c, &k);
	for (int i = 0; i < r; i++)
		cin >> ary[i];
	dfs(0, r-1, 1);
	printf("%d", cnt);

	return 0;
}