[알고리즘] 백준 1189

백준 1189번 컴백홈

해결 과정 요약

dfs를 해주는데 완전탐색을 해야하므로 방문 후에 visited를 다시 0으로 바꾸어준다.
도착지점을 만나면 return을 해주어 재귀함수가 끝나게 해준다.
단, 노드 수를 세어 저장한 cnt값이 K와 같은경우 1을 아닌경우 0을 리턴해준다.
이렇게 dfs함수를 잘 만들기만 하면 문제가 풀린다.

풀이

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

int R,C,K;
string s;
int a[5][5];
int visited[5][5];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

int dfs(int y, int x, int cnt){
    if(y == R-1 && x == C-1){
        if(K == cnt) return 1;
        else return 0;
    }
    int ret = 0;
    visited[y][x] = 1;
    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 || a[ny][nx] || visited[ny][nx]) continue;
        ret += dfs(ny, nx, cnt+1);
    }
    visited[y][x] = 0;
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> R >> C >> K;
    for(int i=R-1; i>=0; i--){
        cin >> s;
        for(int j=0; j<C; j++){
            if(s[j] == 'T') a[i][j] = 1;
        }
    }
    cout << dfs(0, 0, 1);
    return 0;
}

코멘트

완전탐색 문제로 탐색 후 visited를 다시 0으로 만들어주는 것이 핵심.