[실버 1] 백준 1189 - 컴백홈 (파이썬)

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

풀이

• 현재 위치에서 이동 횟수를 세면서 목적지 (0, C-1)에 도달하는 모든 경로의 수를 세는 문제.
• 단, 정확히 K칸 이동한 경로만 유효함.
• 이동은 상하좌우 가능하며, T는 막힌 칸이므로 이동 불가.

1. 시작 위치는 (R-1, 0) 여기가 ‘집’.
2. 목표 위치는 (0, C-1) 여기가 ‘학교’.
3. DFS로 이동 경로를 탐색하면서 K-1번 이동해야 하며, 마지막 위치가 (0, C-1)일 때만 카운트한다.
4. 방문 체크는 used 리스트로 관리한다.
5. 백트래킹으로 이전 경로로 되돌아가 다른 경로 탐색을 계속

used를 리스트 대신 set으로 바꾸면 in 검사 속도가 O(n) → O(1)로 줄어 성능 향상 가능

def dfs(r, c, k, used):
    if k == 0:
        if r == 0 and c == C - 1:
            global answer
            answer += 1
        return
    
    for i in range(4):
        nr, nc = r + dr[i], c + dc[i]
        if 0 <= nr < R and 0 <= nc < C and B[nr][nc] != 'T' and (nr, nc) not in used:
            used.add((nr, nc))
            dfs(nr, nc, k - 1, used)
            used.remove((nr, nc))

dfs(R - 1, 0, K - 1, {(R - 1, 0)})

코드

# 백준 1189 - 컴백홈
# 분류 : 브루트포스

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

dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

answer = 0

def dfs(r, c, k, used) :
    if k == 0 :
        if r == 0 and c == C - 1 :
            global answer
            answer += 1
        return
    
    for i in range(4) :
        nr, nc = r + dr[i], c + dc[i]

        if nr < 0 or R <= nr or nc < 0 or C <= nc :
            continue

        if B[nr][nc] == 'T' :
            continue

        if (nr, nc) not in used :
            used.append((nr, nc))
            dfs(nr, nc, k - 1, used)
            used.pop(-1)

dfs(R - 1, 0, K - 1, [(R - 1, 0)])

print(answer)