1189: 컴백홈 - DFS

https://www.acmicpc.net/problem/1189

1189번: 컴백홈

 

문제요약

왼쪽 아래에서 오른쪽 위 꼭짓점으로 이동할 때, 이동 거리가 k인 경우의 수 구하기

 

난이도

Silver 1

---

풀이 포인트

• 경로의 수 누적하기
• 방문배열 초기화 위치

---

REVIEW

 

방문배열에 이동 거리를 누적해 가는 방법에 익숙해 져야 하고,

재귀가 끝나는 시점에 방문배열을 초기화해줘야 하는데, 이 코드의 위치를 찾기가 힘들었다.

 

한 경로가 끝이나면 방문 배열을 초기화해주고 또 새로운 경로를 탐색토록 해야하는데,

이것이 재귀로 뻗어나가니 실행순서를 파악하는 것이 참 헷갈렸다.

 

아직까진 bfs보다 dfs구현이 쉬워서 기본 코드는 이제 외운듯 하나,

이렇게 활용이 들어가면 자꾸 헤메니 아직 실력이 너무 부족하다..

 

대충의 감은 온 것 같다.

---

CODE

 

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

const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int n, m, k, visited[10][10]; 
char a[10][10];
string s; 

int go(int y, int x){
	
    // 한 경로가 도착지에 다다랐고, k번째 만에 이동했다면 1가지 경우의 수 추가
	if(y == 0 && x == m - 1){
		if(k == visited[y][x]) return 1;
		return 0; 
	}
    
    // k만에 가는 경로의 수 누적
	int ret = 0; 
    
    // 일반 DFS
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny < 0 || nx < 0 || ny >= n || nx >= m || visited[ny][nx] || a[ny][nx] == 'T')continue;
		
        // 방문배열에 이동 거리 누적
        visited[ny][nx] = visited[y][x] + 1; 
        
        // 현재 탐색하는 경로 중 k번째 이동에 성공하면 1이 리턴값으로 누적
		ret += go(ny, nx);
        // 현재 탐색 끝나고 방문배열 초기화
		visited[ny][nx] = 0;
	}
	return ret; 
}
int main(){
	cin >> n >> m >> k; 
	for(int i = 0; i < n; i++){
		cin >> s; 
		for(int j = 0; j < m; j++){
			a[i][j] = s[j];
		}
	} 
	visited[n - 1][0] = 1; 
	cout << go(n - 1, 0) << "\n";
}