[Baekjoon/C++] 1189번 - 컴백홈

[백준] Baekjoon Online Judge

문제로 이동

 

문제

한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f 
      bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde 
      a...  abcd  abc.  abcd  a...  a.gh  abc. 
거리 :  6     6     6     8     8    10    6

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

 

입력

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.

 

출력

첫 줄에 거리가 K인 가짓수를 출력한다.

 

---

풀이

#include <iostream>
using namespace std;

int R, C, K, result = 0;
string arr[5];
bool check[5][5];

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

bool isArrive(int x, int y);
bool canVisit(int x, int y);
void dfs(int x, int y, int cnt);

// 목적지 도착 여부 확인
bool isArrive(int x, int y) {
    return (x == C - 1) && (y == 0);
}

// 이동할 수 있는 칸인지 확인
bool canVisit(int x, int y) {
    if (x < 0 || x >= C || y < 0 || y >= R) return false;
    if (check[y][x] || arr[y][x] == 'T') return false;
    return true;
}

void dfs(int x, int y, int cnt) {
    if (cnt > K) return;

    if (cnt == K && isArrive(x, y)) {
        result++;

        return;
    }

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

        if (canVisit(nx, ny)) {
            check[ny][nx] = true;
            dfs(nx, ny, cnt + 1);
            check[ny][nx] = false;
        }
    }
}

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 >> arr[i];

    check[R - 1][0] = true;
    dfs(0, R - 1, 1);

    cout << result << '\n';

    return 0;
}

 

bool isArrive(int x, int y) {
    return (x == C - 1) && (y == 0);
}

 현재 위치가 목적지인지 확인하는 함수이다.

 

bool canVisit(int x, int y) {
    if (x < 0 || x >= C || y < 0 || y >= R) return false;
    if (check[y][x] || arr[y][x] == 'T') return false;
    return true;
}

 해당 좌표로 이동할 수 있는지 확인하는 함수이다. 배열을 벗어나거나 이미 방문했거나 방문이 불가능한 장소라면 false를 return 한다.

 

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

void dfs(int x, int y, int cnt) {
    if (cnt > K) return;

    if (cnt == K && isArrive(x, y)) {
        result++;

        return;
    }

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

        if (canVisit(nx, ny)) {
            check[ny][nx] = true;
            dfs(nx, ny, cnt + 1);
            check[ny][nx] = false;
        }
    }
}

 깊이우선탐색을 하는 함수이다. 이동거리를 의미하는 cnt가 K와 같아진다면 현재 위치가 목적지인지 확인하고, 목적지라면 result를 1 증가시킨다. 필요없는 탐색을 줄이기 위해 cnt가 K보다 커지게 되면 더 깊은 탐색을 하지 못하도록 했다.