BOJ - 1189 - 컴백홈
문제
문제
한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.
1
2
3
4
cdef ...f ..ef ..gh cdeh cdej ...f
bT.. .T.e .Td. .Tfe bTfg bTfi .Tde
a... abcd abc. abcd a... a.gh abc.
거리 : 6 6 6 8 8 10 6
위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.
입력
첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 ‘.’과 ‘T’로 구성된 길이가 C인 문자열이 주어진다.
출력
첫 줄에 거리가 K인 가짓수를 출력한다.
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
using namespace std;
// map
int n, m, num;
bool map[10][10];
int visited[10][10];
// joy
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
int y, x;
// dfs
int dfs(int y, int x)
{
// 기저사례
// 집은 오른쪽 위에 있다.
if(y == 0 && x == m-1)
{ // 집에 도착하면
if(num == visited[y][x])
return 1;
return 0;
}
int cnt = 0;
for(int i=0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || ny >= n || nx < 0 || nx >= m)
continue;
if(!visited[ny][nx] && !map[ny][nx])
{
visited[ny][nx] = visited[y][x] + 1;
// 목적지에 도착하면
cnt += dfs(ny, nx);
// 지나온 흔적은 지운다.
visited[ny][nx] = 0;
}
}
return cnt;
}
int main()
{
cin >> n >> m >> num;
for(int i=0; i < n; i++)
{
string str;
cin >> str;
for(int j=0; j < m; j++)
if(str[j] == 'T')
map[i][j] = 1;
}
// 한수는 현재 왼쪽 아래점에 있다.
visited[n-1][0] = 1;
cout << dfs(n-1, 0) << endl;
}
SOL
- dfs로 구현하되, bfs와 같이 가중치를 더해준다.
- 지나온 목적지에 도착 하였을 경우
- 목적 거리 num와 맞을 경우
- return 1
- 목적 거리 num와 틀린 경우
- return 0
- 목적 거리 num와 맞을 경우