[백준][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인 가짓수를 출력한다.

 

 

 

예)

Input

3 4 6
....
.T..
....

 

output

4

 

 

 

 

 

 

내 생각

문제요약

1. 한수가 왼쪽 아래에서 오른쪽 위의 집에 돌아간다.

2. 이 때,  지나친 곳은 다시 방문하지 않고, 맵에서 T로 표시된 부분은 갈 수 없다.

3. 한수가 집까지 도착하는 경로 중 거리가 K인 경우의 수 구하라

 

DFS 문제로 방문처리를 해주면서 확인을 해야한다. 현재 지점을 방문했음을 T로 표시하고, 상하좌우로 움직이면서 DFS를 다시 호출해서 탐색한다. DFS 호출이 끝나면 다시 현재 지점을 . 으로 되돌려야 한다!! (다른 방향으로도 다시 탐색해야하기 때문)

이번 문제에서 중요한 부분은 왔던 곳을 T로 막고, 오른쪽 위로 탐색해 나가는 것이다!

 

 

 

코드

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 _ in range(N)]

#(x, y):현재 위치, count: 방문한 수
def DFS(x, y, count):
	# 조건만족
    if count == K and x == 0 and y == M - 1:
        return 1
    paths = 0
    # 상하좌우로 이동 (x-1, y): 상, (x+1, y): 하, (x, y-1): 좌, (x, y+1): 우
    for nx, ny in zip([x-1, x+1, x, x], [y, y, y-1, y+1]):
    	# 맵을 벗어나지 않으면서, .인 곳을 방문
        if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == '.':
        	# 방문한 곳
            graph[nx][ny] = 'T'
            paths += DFS(nx, ny, count + 1)
            #다시 .으로 복구
            graph[nx][ny] = '.'
    return paths

# 시작점인 왼쪽 아래 (N-1, 0)에서 시작
graph[N-1][0] = 'T'
answer = DFS(N-1, 0, 1)
print(answer)

 

 

 

 

*zip

iterable에서 하나씩 원소를 가져와서 튜플로 묶어줌

예)

list1 = [1, 2, 3]
list2 = ['a', 'b', 'c']

result = zip(list1, list2)

 

결과)

[(1, 'a'), (2, 'b'), (3, 'c')]