[백준] 1189 - 컴백홈

1. 문제 이해

2차원 배열의 좌측 아래에서 우측 상단으로 한수가 이동하는데, 그 이동경로는 여러가지가 있다. 방문한 곳을 다시 방문하지 않았다고 한다면 이동경로들의 거리는 전부 똑같지는 않을 것이다.

 

즉, 가장 가까운 거리를 구하는 것이 아닌, 모든 이동경로들의 거리를 구해, K와 거리가 일치하는 수를 구하면 되는 문제이다. 이 때, 거리가 K를 넘어선다면 탐색 할 필요가 없어진다.

---

2. 문제 풀이

2차원 배열에서 모든 이동경로를 구하는 문제이므로, DFS가 적합하다. DFS에서 2차원 배열을 탐색할 때 마다 현재 좌표의 거리만 계속해서 알고 있다면 문제를 풀 수 있다.

 

DFS를 재귀함수로 구현한다면, 3가지만 잘 체크하면 된다.

 

1. 재귀함수 기저사례
   목적지에 도착하면 탐색할 필요가 없으므로 도착지를 기저사례로 삼는다.
2. 백트래킹
   원하고자 하는 거리는 K이므로 K를 넘어서는 거리의 이동경로를 알 필요가 없다.
3. 모든 경로 탐색
   모든 경로를 탐색해야 하므로, DFS로 하나의 이동경로가 만들어졌다면, 그 이동경로에서 방문을 한 점을 방문을 하지 않은 점으로 바꿔준다. 그래야 모든 경로 탐색이 가능하다.

---

3. 제출 결과

---

4. 문제 코드

#include <iostream>
using namespace std;
int visited[10][10];
char board[10][10];
int dir[4][2] = {{1,0}, {0,1}, {-1, 0}, {0, -1}};
int R,C,K;
int ans = 0;

void dfs(int y, int x, int t) {
    if ( t > K) { return;}
    visited[y][x] = t;

    if(y == 0 && x == C -1) {
        if(t == K) { ans++;}
        visited[y][x] = 0;
        return ;
    }

    for(int i=0; i < 4; i++) {
        int dy = y + dir[i][0];
        int dx = x + dir[i][1];

        if(dy < 0 || dx < 0 || dy >= R || dx >= C || visited[dy][dx] != 0 || board[dy][dx] == 'T') {
            continue;
        }

        dfs(dy, dx, t+1);
    }
    visited[y][x] = 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> R >> C >> K;

    for(int i=0; i<R; i++) {
        cin >> board[i];
    }
    dfs(R-1,0,1);
    cout << ans ;
}