[백준] 1189번: 컴백홈 문제 풀이

문제

한수는 캠프를 마치고 집에 돌아가려 한다. 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다. 그리고 한수는 집에 돌아가는 방법이 다양하다. 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. T로 표시된 부분은 가지 못하는 부분이다. 문제는 R x C 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지도 도착하는 경우 중 거리가 K인 가짓수를 구하는 것이다.

입력

첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다.

출력

첫 줄에 거리가 K인 가짓수를 출력한다.

접근 방식

문제를 읽자마자 우선 탐색으로 접근해보기로 했다.
우선 탐색을 이용하면 최단거리는 쉽게 구할 수 있었으나, 모든 거리 별 경로의 가짓 수는 구하는 데에 한계가 있었다.
때문에 우선 탐색에 재귀 함수를 섞어서 각 경로별로 이동한 거리와 방문 내역을 인자로 넘겨주기로 했다.

문제 풀이
1. 시작점(왼쪽 아래)부터 dfs를 호출한다.
2. 해당 위치에서 네 방향을 조사한다.
3. 이동하려는 위치가 범위 내에 있고, 해당 경로에서 방문한 적이 없으며, T가 아닐 경우 해당 위치, 현재 이동한 거리, 해당 경로의 방문내역을 인자로 하여 dfs를 재귀적으로 호출한다.
4. 현재 위치가 집(오른쪽 위)라면 딕셔너리에 해당 거리를 키로 하여 1씩 추가한다.

3, 4를 코드로 구현하면 다음과 같다

if 0 <= nx < R and 0 <= ny < C and load[nx][ny] != 'T' and [nx, ny] not in visited:
    # 이동할 위치와, cnt+1, 각각의 방문 내역을 따로 주어 재귀 호출
    dfs(nx, ny, cnt + 1, visited + [nx, ny])

전체 코드

# 좌, 상, 우, 하 방향 리스트
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

def dfs(x, y, cnt, visited):
    # 현재 위치를 visited에 추가
    visited.append([x, y])

    # 현재 위치가 집(오른쪽 위)라면 딕셔너리에 cnt += 1
    if x == 0 and y == C-1:
        if cnt in dict:
            dict[cnt] += 1
        else:
            dict[cnt] = 1
        return

    # 상하좌우 모든 방향에 대해
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 이동하려는 곳이 범위 내에 있고, T가 아니고, 방문했던 적이 없다면
        if 0 <= nx < R and 0 <= ny < C and load[nx][ny] != 'T' and [nx, ny] not in visited:
            # 이동할 위치와, cnt+1, 각각의 방문 내역을 따로 주어 재귀 호출
            dfs(nx, ny, cnt + 1, visited + [nx, ny])


R, C, K = map(int, input().split())
load = []
dict = {}

for _ in range(R):
    load.append(input())

# 시작 위치(왼쪽 아래)에서 함수 호출
dfs(R-1, 0, 1, [])

# 거리가 K인 경우의 수가 있으면 가짓수 출력
print(dict[K] if K in dict else 0)

굳이 재귀 함수를 섞지 않고 우선 탐색만으로 푸는 방법이 있을 것 같다.
그렇게 하면 연산 시간을 더 빠르게 할 수 있을텐데...