[BOJ]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를 사용해서 시작점에서 도착점까지 이동하고, 한 번의 이동마다 거리를 하나씩 늘린다. 도착점에 도달한 경우 거리가 K와 같다면 answer를 하나 증가시키고, 그렇지 않다면 다시 되돌아 오는 과정을 수행한다. '다시 되돌아 온다' 라는 행동을 하기 위해 visited 배열을 사용하고, 그 위치로 이동한 경우에는 해당 좌표의 값을 1로 바꾸고, 다시 되돌아 온 경우에는 0으로 다시 바꿔주도록 한다.

dx = [-1, 0 , 1, 0]
dy = [0, -1, 0 , 1]
 
from collections import deque
 
def dfs(x, y, count):
    global answer
    visited[x][y]=1
    if [x,y]==[0, C-1]:
        if count==K:
            answer+=1
        return
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx < R and 0 <= ny < C  and visited[nx][ny]==0 and maps[nx][ny]!='T':
            visited[nx][ny]=1
            dfs(nx,ny,count+1)
            visited[nx][ny]=0
            
R, C, K = map(int,input().split())
maps = [list(input()) for _ in range(R)]
visited = [[0 for _ in range(C)] for _ in range(R)]
answer= 0
dfs(R-1, 0, 1)
print(answer)

문제링크:

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

1189번: 컴백홈