[백준/BOJ] 1189번 컴백홈

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

1189번: 컴백홈

백트래킹을 이용하여 경로의 모든 경우의 수를 구한 후, 거리가 K인 개수를 구하는 문제이다.

(DFS 구현시, 반환값이 있는 형태로 만드는 연습이 필요한 것 같다.)

 

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

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

int n, m, k;
char area[11][11];
int visited[11][11];

int DFS(int x, int y, int d) {
	if(x == 0 && y == m - 1) {
		if(k == d) return 1;
		return 0;
	}
	
	int ret = 0;
	for(int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(nx < 0 || nx >= n || ny < 0 || ny >= m || area[nx][ny] == 'T' || visited[nx][ny] == 1) continue;
		visited[nx][ny] = 1;
		ret += DFS(nx, ny, d + 1);
		visited[nx][ny] = 0;
	}
	
	return ret;
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n >> m >> k;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cin >> area[i][j];
		}
	}
	
	visited[n - 1][0] = 1;
	cout << DFS(n - 1, 0, 1);
}

 

#include<bits/stdc++.h>
#define f first
#define s second
#define lp1(i, x, n) for(int i = x; i <= n; i++)
using namespace std;
typedef long long ll;

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

int t, n, m, h, k, r, c, sx, sy, ex, ey, x, y, z, answer = 2147000000, L, R, flag, sum;
char board[11][11];
int visited[11][11], res[31];

void DFS(int _x1, int _y1, int _x2, int _y2, int cnt) {
    if (_x1 == _x2 && _y1 == _y2) {
        res[cnt]++;
        return;
    }
    
    for(int i = 0; i < 4; i++) {
        int nx = _x1 + dx[i];
        int ny = _y1 + dy[i];
        if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
        if(visited[nx][ny] || board[nx][ny] == 'T') continue;
        visited[nx][ny] = 1;
        DFS(nx, ny, _x2, _y2, cnt + 1);
        visited[nx][ny] = 0;
    }
}

int main() {
	//freopen("input.txt", "r", stdin);
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> r >> c >> k;
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++) {
            cin >> board[i][j];
        }
    }
    sx = r - 1, sy = 0;
    ex = 0, ey = c - 1;
    if(board[sx][sy] == 'T' || board[ex][ey] == 'T') {
        cout << "0";
        return 0;
    }
    visited[sx][sy] = 1;
    DFS(sx, sy, ex, ey, 1);
    cout << res[k];
}