[완전탐색 / BOJ 1189 / C++] 컴백홈

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

1189번: 컴백홈

1) find_rt함수를 재귀적으로 실행해준다. (bfs나 dfs처럼 동작)
1-1) base 조건은 x,y가 목적지에 도달했고 여기까지 온 비용이 K와 동일할때 1를 리턴한다.
1-2) 비용이 K와 동일하지 않다면, 0을 리턴한다.
 1-3) 목적지에 아직 도달하지 않았다면, 목적지까지 네 방향으로 순회한다.

난 먼가 어려웠다... bfs나 dfs는 공식대로 하면 다 해결됐는데 이건 bfs이면서 아니라서 아이디어가 잘 떠오르지 않았다..

 

이 문제의 가장 중요한 것은 bfs를 돌면서, 만약 목적지에 도달했다면 리턴해주고 목적지까지 도달하기 까지 지나온 

장소들의 방문을 모두 해제하는 것이다. (엄밀히말하면 bfs는 아니다)

 

그렇게해서, 다른 경우의 수도 세줄 수 있는 것이다. 

 

또한 함수는 void형이 아닌 int형을 리턴한다!!! 

 

이를 통해서 계속해서 개수를 갱신해나갈 수 있다. 이건 이전에 풀었던 문제들과 맥락이 비슷하다.

 

#include <bits/stdc++.h>

using namespace std;

int R, C, K;
string s;
char bd[26][26];
int vis[26][26];

int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, -1, 0, 1};

int find_rt(int y, int x){
    if(y==0 && x==C-1) {
        if(K==vis[y][x]) return 1;
        return 0;
        
    } // vis[y][x]가 K이고 끝점 도달시 1 리턴하고 종료 (아니면 0)
    
    int cnt = 0; // 개수 초기화.
    
    for(int i = 0 ; i < 4 ; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        if(ny >= R || nx >= C || ny < 0 || nx < 0 || bd[ny][nx]=='T' || vis[ny][nx]) continue; // 불가 조건이면 종료
        
        vis[ny][nx] = vis[y][x] + 1;
        
        cnt += find_rt(ny, nx); // 개수 세기
        
        vis[ny][nx] = 0; // vis풀어주기 (다음 경우의 수 세기 위해서)
        
        
    }
    
    
    return cnt;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> R >> C >> K;
    
    for(int i = 0 ; i < R ; i++){
        cin >> s;
        for(int j = 0 ; j < C ; j++){
            bd[i][j] = s[j];
        }
    }
    
    vis[R-1][0]=1;
  
    cout << find_rt(R-1, 0);
    
        
    
 
}