[백준 1189번] 파이썬 - 컴백홈

백준 1189_컴백홈

시간제한 1초, 메모리 제한 128MB

# 조건

• 한수는 캠프를 마치고 집에 돌아가려 한다.

• 한수는 현재 왼쪽 아래점에 있고 집은 오른쪽 위에 있다.

• 그리고 한수는 집에 돌아가는 방법이 다양하다.

  • 단, 한수는 똑똑하여 한번 지나친 곳을 다시 방문하지는 않는다.

• 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를 사용하여 풀어줄 수 있다.
• 또한, 백트래킹을 사용하여 해를 도출한 이후 다시 원상태로 복구 해주며 다른 길을 찾아준다.
• 카운트가 k == K인 경우 집인지 체크해주면 된다.

import sys
input=sys.stdin.readline

dx=[-1,1,0,0]
dy=[0,0,-1,1]
N,M,K=map(int,input().split())

graph=[ list(input().rstrip()) for i in range(N) ] 

answer=0


def DFS(x,y,count):
    global answer

    if count==K and x==0 and y==M-1:
        answer+=1
    else:
        for i in range(4):
            nx=x+dx[i] ; ny=y+dy[i]

            if 0<=nx<N and 0<=ny<M and graph[nx][ny]=='.':
                graph[nx][ny]='T'
                DFS(nx,ny,count+1) 
                graph[nx][ny]='.' #이미왔던 지점은 막아주는대신에 , 끝까지 탐색한후에는 원래되로 되돌려놓는다. 

graph[N-1][0]='T'
DFS(N-1,0,1)
print(answer)