[Python]백준 1189번/컴백홈/백트래킹/dfs

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

1189번: 컴백홈

⚡️ 문제 설명

R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면

한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것

⚡️ 해결 방법

시작점은 (r-1,0)

도착점은 (0,c-1)

시작점 ~ 도착점 까지 거리가 k 인 가짓수를 구하는 문제이다.

 

백트래킹 문제를 풀어봤다면 쉽게 풀 수 있는 문제였다.

백트래킹은 한정 조건을 가진 문제를 해결하는 전략으로, 탐색을 줄일 수 있다.

DFS는 모든 경우를 탐색하지만, 백트래킹+DFS는 불필요한 탐색을 하지 않는다. 

백트래킹은 BFS와 DFS와 모두 구현이 가능하지만, 조건에 부합하지 않으면 이전 노드로 돌아와야하기 때문에 구조적으로 DFS구현이 편하다.

 

이 문제에서 백트래킹 한정조건은 

graph[nx][ny] == '.' 이다.

'.' 일 때 '.'을 'T'로 바꿔 방문처리를 하고 탐색을 시작한다.

탐색이 끝나면 'T'를 '.'로 돌려 놓아 다른방향으로 다시 탐색 하도록 한다.

 

⚡️ 코드

import sys
input = sys.stdin.readline

# r X c  맵
# 거리가 k 인 가짓수 구하기
r,c,k = map(int, input().split())
graph = []
for _ in range(r):
    graph.append(list(input().rstrip()))

dx = [1,-1,0,0]
dy = [0,0,1,-1]

answer = 0
def dfs(x,y,distance):
    global answer
    # 목표 도착 지점 : (0,c-1)
    # 목표 거리 : k
    if distance == k and y == c-1 and x==0:
        answer += 1
    else:
        # T로 방문처리
        graph[x][y]='T'
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            # 백트래킹 한정 조건 : graph[nx][ny] == '.'
            if(0 <= nx < r and 0 <= ny < c and graph[nx][ny] == '.'):
                graph[nx][ny]='T'
                dfs(nx,ny,distance+1)
                # 원래 상태로 돌려 놓아 다른 방향으로 다시 탐색하도록 한다.
                graph[nx][ny]='.'

# 시작점 : (r-1,0)
# 초기 distance : 1
dfs(r-1,0,1)
# 정답
print(answer)