[백준] 1189 : 컴백홈 (Python)

 

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

 

문제

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

      cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f 
      bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde 
      a...  abcd  abc.  abcd  a...  a.gh  abc. 
거리 :  6     6     6     8     8    10    6

위 예제는 한수가 집에 돌아갈 수 있는 모든 경우를 나타낸 것이다. 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인 가짓수를 출력한다.

 

---

 

아이디어

 

경로의 가지수를 묻는 문제이므로, 그래프 탐색임을 알 수 있다. 그래프 탐색은 DFS와 BFS 2가지로 나뉘므로, 어떤 기법을 선택하는 것이 좋을까?

 

경로 길이 관점

BFS는 목표점까지의 경로가 최단임을 보장하는 탐색 기법이다. 최소 길이를 요구하는 문제에서는 적합할 수 있다. 그러나, 현 문제에서는 지정된 거리를 찾아야 하기에, 최단 경로가 정답이 아닐 수 있으므로 해당 기법은 적절하지 않다고 해석할 수 있다.

 

거리 저장 관점

거리를 저장하는 방식의 고려사항은 '특정 노드까지 도달하는데 많은 경우의 수가 존재하는가' 이다. 다음의 사진을 살펴보자.

노드 d까지 올 수 있는 경로의 가짓수

 

좌표 d까지 가능한 경로는 상/하/우 3가지가 존재한다. 다시 말해, 원하는 k거리인지 체크하기 위해서는 방문배열 겸 거리를 저장하는 visited 배열이 필요하고, 이는 3차원 배열로 설정할 수 밖에 없다.

visited[x][y][z]라 가정시, x,y,z의 의미는 다음과 같다.

• (x,y) == (행,열)
• z : 상하좌우를 나타내는 1차원 배열
• ex) visited[d좌표 x][d좌표 y][상|하|좌|우 인덱스] = 현재 경로 길이

그러므로, 메모리 공간 효율이 떨어지기에, BFS의 특성을 살릴 수 없다. 결국, 모든 경로에 대해 백트래킹이라는 특징을 가진 DFS가 현 문제에서는 효율적이란 사실을 알 수 있다.

 

정답 코드

# https://www.acmicpc.net/problem/1189
# 컴백홈
# 그래프 탐색, 백트래킹, 브루트포스, dfs

input=__import__('sys').stdin.readline

def dfs(sx,sy,cnt):
    global answer

    if (sx,sy)==(0,c-1) and cnt==k:
        answer+=1
        return
    
    for dx,dy in [(-1,0),(0,1),(0,-1),(1,0)]: #상우좌하
        nx,ny=sx+dx,sy+dy
        if 0<=nx<r and 0<=ny<c:
            if board[nx][ny]=='.' and visited[nx][ny]==0:
                visited[nx][ny]=1
                dfs(nx,ny,cnt+1)
                visited[nx][ny]=0

r,c,k=map(int,input().split())
visited=[[0]*c for _ in range(r)]
visited[r-1][0]=1
board=[[*input()][:-1] for _ in range(r)]
answer=0

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