(C++) - 백준(BOJ) 1189번 : 컴백홈 답

www.acmicpc.net/problem/1189

1189번: 컴백홈

dfs를 이용해 구현 할 수 있는 문제였습니다.

풀이방법

 1. T인경우 이거나 이미 방문한 경우에는 갈 수 없는 길입니다.

 2. 방문을 한 후 dfs를 또 호출해 다음 길로 가며 호출 후에는 해당 길 방문했던 기록을 없앰으로써 다른 경로에서 온 경우를 제하는 것을 방지합니다.

Code

#include <bits/stdc++.h>
using namespace std;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
char region[6][6];
int ck[6][6];
int r,c,k, ans;
void dfs(int x, int y, int distance){
    if(distance == k && x == 0 && y == c - 1) 
        {ans ++; return;}
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(region[nx][ny] == 'T') continue;
        if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
        if(ck[nx][ny]) continue;
        ck[nx][ny] = 1;
        dfs(nx, ny, distance + 1);
        ck[nx][ny] = 0;
    }
}

int main(){
    cin >> r >> c >> k;
    for(int i = 0; i < r; i++)
        for(int j = 0 ;j < c; j++) 
            cin >> region[i][j];
    ck[r-1][0] = 1;
    dfs(r-1,0,1);   
    cout << ans <<'\n';
}