(백준-1189) 컴백홈 - 파이썬

영관·2023년 3월 7일

DFS 그래프이론 그래프탐색 깊이우선탐색 백준1189 백트래킹 파이썬

백준문제

목록 보기

6/11

문제 (백준-1189 컴백홈)

문제 출처 : https://www.acmicpc.net/problem/1189

문제 이해

조건

한수의 위치는 가장 왼쪽 아래에 있다.
한수의 집은 가장 오른쪽 위에 있다.
T인 지점은 이동할 수 없다.
한수는 똑똑해서 방문했던 곳을 다시 방문하지 않는다.

구할 것

R: 행의 갯수, C: 열의 갯수, K: 도착하는 거리가 주어졌을 때 한수가 집에 도착하는 길의 경우의 수 중에서 K거리만에 한수의 집에 도착하는 가짓수를 출력합니다.

접근

문제의 형태만 보아도 그래프 탐색의 문제같이 보입니다 ㅎㅎㅎ

문제에서 나타난 예시로 케이스를 살펴보겠습니다.

아직 한수가 집에 출발하지 않은 초기 그래프상태입니다.

한수가 이동할 수 있는 케이스 1번입니다. (거리 6)

한수가 이동할 수 있는 케이스 2번입니다. (거리 10)

한수가 이동할 수 있는 케이스 3번입니다. (거리 8)
한수가 이동할 수 있는 케이스 4번입니다. (거리 6)
한수가 이동할 수 있는 케이스 5번입니다. (거리 8)
한수가 이동할 수 있는 케이스 6번입니다. (거리 6)
한수가 이동할 수 있는 케이스 7번입니다. (거리 6)

모든케이스들을 살펴보았습니다. R은 3 C는 4일때 한수가 이동할 수 있는 경로들과 집에 도달할 때까지의 거리들입니다.

이 케이스에서는 K는 6이기 때문에 위에 살펴본 케이스 중 1, 4, 6, 7번의 케이스가 해당되기 때문에 가짓수는 4이므로 정답은 4가 되는 것입니다.

어떻게 구현해볼 수 있을까요?

DFS(깊이 우선 탐색), 백트래킹을 이용하여 방문하지 않고 T가 아닌 부분으로 한수가 이동하도록 하면 됩니다!

여기서 방문처리는 한수가 이동한 거리로 갱신하여 처리를 했습니다.

코드

import sys

input = sys.stdin.readline


# r: 행, c: 열, k: 거리
r, c, k = map(int, input().strip().split())
graph = []
for _ in range(r):
    graph.append(list(input().strip()))

# 상, 우, 하, 좌
move = [[-1, 0], [0, 1], [1, 0], [0, -1]]

# 처음 한수의 위치를 1로 설정
graph[r - 1][0] = 1

# 가짓수를 세기 위한 변수
result = 0
# 집은 오른쪽 맨 위임
def dfs(row, col):
    global result
    # 한수가 집에 도달했을 경우
    if row == 0 and col == c - 1:
    	# k와 한수가 이동한 거리가 동일하다면 가짓수에 넣어줍니다.
        if graph[row][col] == k:
            result += 1
            return
        else:
            return
    for i in move:
        nrow = row + i[0]
        ncol = col + i[1]
        if nrow >= 0 and ncol >= 0 and nrow < r and ncol < c:
            if graph[nrow][ncol] == '.':
                graph[nrow][ncol] = graph[row][col] + 1
                dfs(nrow, ncol)
                # 다음의 케이스에서 이용하기 위해서 방문처리를 해제해줍니다.
                graph[nrow][ncol] = '.'


dfs(r - 1, 0)
print(result)