[파이썬/Python] 백준 1189(🥈1): 컴백홈

숨·2025년 8월 8일

코테

알고리즘 문제 풀이

목록 보기

107/128

📌 문제 : 백준 1189

📌 문제 탐색하기

R, C : 맵의 크기 ( $1 ≤ R ≤ 5, 1 ≤ C ≤ 5$ )
K : 찾으려는 거리

문제 풀이

왼쪽 아래에서 시작해서 오른쪽 위까지 R×C 크기의 맵을 이동할 수 있는 경우의 수를 구하고, 그 중 거리가 K인 경우의 수의 가짓수를 구하는 문제이다.

DFS를 활용해 시작점에서 끝점까지 이동하는 모든 경우의 수를 구하면서 문제에 따라 종료 조건을 구성해 불필요한 연산을 줄이는 방향으로 구현한다.

최단 거리가 아닌 K 거리를 이동하는 모든 가짓수를 구해야 하므로 BFS보다 DFS를 선택했다.

이동은 상하좌우로 하기에 4가지 방향을 정의한다.
지나친 곳은 다시 방문하지 않으므로 방문한 곳을 저장해야 한다 → 방문 리스트 정의 필요!

DFS 이용

DFS 탐색 조건은 다음과 같이 정의한다.

R×C 범위 내
해당 위치의 정보가 T가 아닌 경우
종료 조건
- 이동 거리가 K를 초과할 경우
- K를 초과하지 않으면서 목적지에 도착했을 경우
‼️ Backtracking 적용 부분 → 방문 해제하기
- 현재 탐색하는 경로에선 방문한 곳을 재방문 하지 않지만 다른 경로에선 방문할 수 있도록 함
- 즉, 여러 경로를 확인해야 하므로 해제 적용

가능한 시간복잡도

이동 거리의 최대인 K는 $R×C$ → $O(𝑅𝐶!)$
경우의 수는 중복 없이 순서 있는 K개 선택 문제와 동일하므로 순열의 개수가 됨 → $O\left( \frac{(RC)!}{(RC - K)!} \right)$

최종 시간복잡도
최악일 때 장애물이 하나도 없어 모든 칸에서 경우의 수를 탐색해야 하므로 $O\left( \frac{(RC)!}{(RC - RC)!}\right)=O((RC)!) = O(25!)$ 이 되는데 이는 충분히 수행 가능하다.

알고리즘 선택

DFS로 하면서 종료조건으로 불필요한 탐색 방지
백트래킹으로 여러 경로 확인할 때 방문 리스트 반복 사용 가능하도록 진행

📌 코드 설계하기

DFS 구현
1-1. 도착점 도착 시 탐색 종료
1-2. 거리가 K 초과 시 탐색 종료
1-3. 4방향 탐색하면서 범위 초과하지 않고 방문한 적 없으며 이동 가능한 위치 이동해 탐색 반복
DFS 수행

📌 시도 회차 수정 사항

1회차

RecursionError: maximum recursion depth exceeded in comparison 발생
종료 조건을 잘못 작성해 무한 재귀 발생
도착했을 때 return해서 탐색 종료해야 하고 K가 넘었을 때도 종료시켜야 하는데 그부분이 빠져 에러 발생

2회차

다른 종료 조건 고려하다가 정작 방문 여부 확인 부분을 누락해서 이를 추가했다.

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline

# dfs 정의
def dfs(x, y, current_distance):
    global answer

    # 종료 조건 1 : 도착점에 도착
    if (x, y) == (end_x, end_y):
        if current_distance == K:
            answer += 1
        return  # 도착했으니 탐색 종료

    # 종료 조건 2 : 거리가 K 넘음
    if current_distance > K:
        return

    # 4방향 탐색
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        # 범위와 맵 정보 확인
        if 0 <= nx < R and 0 <= ny < C and not visited[nx][ny] and map_info[nx][ny] != 'T':
            visited[nx][ny] = True
            dfs(nx, ny, current_distance+1)
            visited[nx][ny] = False


# 입력 받기
R, C, K = map(int, input().split())
map_info = [list(input().rstrip()) for _ in range(R)]

# 방문 리스트 정의
visited = [[False] * C for _ in range(R)]

# 정답 변수 초기화
answer = 0

# 이동 방향 정의
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

# 왼쪽 아래부터 오른쪽 위로 이동
start_x, start_y = R - 1, 0
end_x, end_y = 0, C - 1

# 시작점 방문 처리
visited[start_x][start_y] = True

# DFS 수행
dfs(start_x, start_y, 1)

# 정답 출력
print(answer)

결과

✏️ 회고

계속 DFS 구현 코드를 잘 떠올리지 못하고 BFS랑 헷갈리고 있다.
DFS/BFS 모두 뼈대 구조를 직접 적어보면서 차이점을 체득해야 겠다.
백트래킹이 단순 종료 조건에 대한 내용이라고 생각했는데 이렇게 여러 경우를 고려해야 할 때도 사용할 수 있는 내용이라는 것을 이 문제로 체감했다. 뭐든 단순하게만 생각하는 것을 경계해야 겠다.