[백준] 1189번 컴백홈 C++ 코드

코드

#include <bits/stdc++.h>
using namespace std;
int n,m,k,visited[10][10],res;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
char a[10][10];
string s;
void go(int x, int y, int cnt) {
  if (cnt == k) {
    if (x==0 && y == m-1) res++;
    return;
  }
  for(int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if(nx >= n || ny >= m || nx < 0 || ny < 0 || visited[nx][ny] || a[nx][ny] == 'T') continue;
    visited[nx][ny] = 1;
    go(nx,ny,cnt+1);
    visited[nx][ny] = 0;
  }
}

int main() {
  cin >> n >> m >> k;
  for(int i = 0; i < n; i++) {
    cin >> s;
    for(int j = 0; j < m; j++) {
      a[i][j] = s[j];
    }
  }
  visited[n-1][0] = 1;
  go(n-1,0,1);
  cout << res << '\n';
  return 0;
}

탐색 후 원상복구를 하면서 길을 찾아가면 되는 문제. nx와 ny를 전역변수로 선언해 테스트케이스가 통과되지 않았는데, 이유는 생각해봐야할 거 같다.