BOJ 1189 - 컴백홈 링크
(2024.03.09 기준 S1)

문제

$R \times C$ 맵에서 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 못가는 부분이 주어지고 거리 $K$가 주어지면, 한수가 집까지도 도착하는 경우 중 거리가 $K$인 가짓수 출력

알고리즘

간단한 백트래킹

풀이

$R$과 $C$의 제한이 $5$밖에 되지 않는다. 그러므로 왼쪽 아래점인 $(R-1, 0)$부터 백트래킹으로 진행하면서 거리가 $K$가 되었을 때의 지점이 $(0, C-1)$인지 확인하면 된다.

주의사항

일반적인 문제에선 시작점의 거리는 $0$이다. 하지만 이 문제의 지문을 보면 시작점의 거리는 $1$이다. 주의하자.

코드

• C++

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

typedef pair<int, int> pii;

const int MAX = 5;
const pii dir[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

int R, C, K;
string matrix[MAX];
bool visited[MAX][MAX];

// 방문하지 않은 곳으로 이동하다가 k가 K일 때 현재 위치가 집인지 확인
int dfs(int k, int r, int c){
    if (k == K){
        return r == 0 && c == C - 1;
    }
    int res = 0;
    for (auto [dr, dc]: dir)
        if (0 <= r + dr && r + dr < R && 0 <= c + dc && c + dc < C && matrix[r + dr][c + dc] == '.' && !visited[r + dr][c + dc]){
            visited[r + dr][c + dc] = true;
            res += dfs(k + 1, r + dr, c + dc);
            visited[r + dr][c + dc] = false;
        }
    return res;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> R >> C >> K;
    for (int i = 0; i < R; i++) cin >> matrix[i];

    fill(&visited[0][0], &visited[R - 1][C], false);
    visited[R - 1][0] = true;
    cout << dfs(1, R - 1, 0);
}

• Python

import sys; input = sys.stdin.readline
dir = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# 방문하지 않은 곳으로 이동하다가 k가 K일 때 현재 위치가 집인지 확인
def dfs(k, r, c):
    if k == K:
        if r == 0 and c == C - 1:
            return 1
        return 0
    res = 0
    for dr, dc in dir:
        if 0 <= r + dr < R and 0 <= c + dc < C and matrix[r + dr][c + dc] == '.' and not visited[r + dr][c + dc]:
            visited[r + dr][c + dc] = True
            res += dfs(k + 1, r + dr, c + dc)
            visited[r + dr][c + dc] = False
    return res

R, C, K = map(int, input().split())
matrix = [input().strip() for _ in range(R)]

visited = [[False] * C for _ in range(R)]
visited[R - 1][0] = True
print(dfs(1, R - 1, 0))