[BOJ] 1189 - 컴백홈

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

BOJ - 컴백홈

문제 유형: 백트래킹

문제 난이도: Silver I

시간 제한: 2초

메모리 제한: 128MB

 

문제

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

      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인 가짓수를 출력한다.

 

풀이

백트래킹을 해주면 된다. 행렬 좌표를 (a, b)면 a행b열이라 하겠다.

(r-1, 0)에서 다음의 dfs를 한다:

만약 거리가 k가 되었고 목적지 (0, c-1)에 도착했다면 ans를 1 늘리면 된다.

혹시 그게 아님에도 k 이상인 경로가 있으면 그만두면 된다.

현재 위치에서 상하좌우방향으로 인접한 칸이 유효한 위치이고 방문한 적 없고 'T'아니라면, 방문처리 하고 재귀로 탐색하고, 방문처리를 해제해주면 된다.

 

최종 ans를 출력한다.

 

코드

C++

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

int r, c, k;
int ans = 0;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void dfs(int x, int y, int dist, vector<string> &mat,
         vector<vector<bool>> &visited) {
  if (x == 0 && y == c - 1 && dist == k) {
    ans++;
    return;
  }
  if (dist > k)
    return;

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

    if (nx < 0 || nx >= r || ny < 0 || ny >= c)
      continue;
    if (mat[nx][ny] == 'T')
      continue;
    if (visited[nx][ny])
      continue;

    visited[nx][ny] = true;
    dfs(nx, ny, dist + 1, mat, visited);
    visited[nx][ny] = false;
  }
}

int main(int argc, char *argv[]) {
  cin >> r >> c >> k;
  vector<string> mat(r);
  for (int i = 0; i < r; ++i) {
    cin >> mat[i];
  }
  vector<vector<bool>> visited(r, vector<bool>(c, false));

  visited[r - 1][0] = true;
  dfs(r - 1, 0, 1, mat, visited);

  cout << ans << "\n";

  return 0;
}