[C++] 백준- 1189 컴백홈 (완전탐색 + DFS)

1. 문제

2. 조건

여기에서 내가 고민했던 점은 이 문제는 기존의 최단거리만을 구하던 BFS문제들과는 다르다는 점이다. 이동하는 거리는 상관이 없고 그저 제약 조건이라고는 T로 표시된 곳은 지나가지 못한다. 또한 갔던 곳은 지나가지 못한다는 점이다. 

따라서 출발점에서 도착점까지 이동할 수 있는 모든 경우의 수를 탐색하여 거리를 구하고 내가 원하는 거리에 해당하는 경로의 수를 출력해야하는 완전탐색 문제였다. 그래서 나는 재귀함수를 이용해서 이 문제를 해결하였다. 

3. 풀이 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int R, C;
int K;
char map[10][10];
int visited[10][10];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
string s;
int dfs(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 || nx < 0 || ny >= R || nx >= C || visited[ny][nx] || map[ny][nx] == 'T')continue; 
		visited[ny][nx] = visited[y][x] + 1;
		ret += dfs(ny, nx);
		visited[ny][nx] = 0;
	}
	return ret;
}
int main() {

	cin >> R >> C >> K;

	for (int i = 0; i < R; i++) {
		cin >> s;
		for (int j = 0; j < C; j++) {
			map[i][j] = s[j];
		}
	}
	visited[R - 1][0] = 1;
	cout << dfs(R - 1, 0) << "\n";


}

내가 해결한 코드는 위와 같다. 우선 기본적으로 경로를 탐색해야하기 때문에 dfs처럼 인덱스 방향 4방향을 탐색하는 DFS함수를 기반으로 했다. 하지만 차이점이라면 경로가 존재한다면 dfs함수가 1을 return하고 없다면 0을 리턴하여 재귀함수를 통해 거리가 K만큼인 경로의 수를 출력할 수 있게 했다는 점이다. 기존의 연결된 컴포넌트와 같은 문제만을 해결하던 dfs에서 벗어나 재귀함수를 이용해 완전탐색 코드로 변형을 했다. 

나는 재귀함수가 어떻게 돌아가는 지 확인하기 위해 디버거를 돌려보았는데 결과는 다음과 같다. 

우선 입력한 map은 가로 3 세로 4 내가 원하는 경로는 6인 입력이었다. 

 

그림으로 나타내면 다음과 같다. 

			도착 점
	T
시작점

디버거를 돌려본 결과를 표로 나타내면 다음과 같다. 

	Y좌표	X좌표	ny좌표	nx좌표	visited[ny][nx]값	visited[y][x]
	2	0	2	-1	0	1
	2	0	3	0	0	1
이동	2	0	2	1	0 -> 1+1=2	1
	2	1	2	0	0	2
	2	1	3	1	0	2
이동	2	1	2	2	0->2+1=3	2
	2	2	2	1	2	3
	2	2	3	2	0	3
이동	2	2	2	3	0->3+1=4	3
	2	3	2	2	3	4
	2	3	3	3	0	4
	2	3	2	4	0	4
이동	2	3	1	3	0->4+1=5	4
이동	1	3	1	2	0->5+1=6	5
	1	2	1	1	0	6 T여서 건너뜀
	1	2	2	2	3	6
	1	2	1	3	5	6
이동	1	2	0	2	0->6+1=7	6
이동	0	2	0	1	0->7+1=8	7
이동	0	1	0	0	0->8+1=9	8
	0	0	0	-1	0	9
이동	0	0	1	0	0->9+1=10	9
	1	0	1	-1	0	10
	1	0	2	0	1	10
	1	0	1	1	0	10 T 건너뜀
	1	0	0	0	0	4번을 돌면 ret
	리턴 시작
	0	0	0	1	8	9
	0	0	-1	0	0	9
	ret = 0	visited[0][0] = 0	0 0인덱스에서	앞서 두번을 돔	나머지 두 번 돌며	탐색
	0	1	1	1	0	8
	0	1	0	2	7	8
	0	1	-1	1	0	8
	ret= 0	visited[0][1] = 0
	0	2	1	2		6
	0	2	0	3	0
	ret = 0	visited[0][3] = 0
	0	2	-1	2
	ret = 0
	ret = 0	visited[1][2] = 0
	1	3	2	3	4
	1	3	1	4
	1	3	0	3
	ret = 1	visited[0][3] = 0

위의 표는 하나의 경로를 탐색하기까지 인덱스의 이동이다. 재귀함수의 인덱스를 살펴보면 for문을 다 돌기전에 재귀함수를 호출하여 다시 재귀함수로 돌아가게되면 for문의 나머지 부분을 리턴할 때 돌면서 한 인덱스 당 4번의 for문을 채우는 것을 확인할 수 있다. 

모든 for문을 건너뛰는 것 없이 돌기 때문에 결국에는 도착점으로 갈 수 있는 모든 경우의 수를 탐색하게 된다. 왜냐하면 한 인덱스 당 가능한 방향을 모두 탐색하기 때문이다. 

따라서 결과는 다음과 같이 나온다. 

4. 결과