[BaekJoon] "DFS/BFS" - 백준 1189번 문제 : 컴백홈

[문제 설명]

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

1189번: 컴백홈

 

한수는 캠프를 마치고 집에 돌아가야 함

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

한수는 집에 돌아가는 방법이 다양하고, 한번 지나친 곳을 다시 방문하지 않음

T로 표시된 부분은 가지 못하는 부분임

RxC 맵에 못가는 부분이 주어지고 거리 K가 주어지면 한수가 집까지 도착하는 경우 중 거리가 K인 가짓수를 구함

 

[해결 로직]

- DFS를 써야함! 

- 왜냐면 DFS 재귀로 모든 경우의 수를 만들고 도착지점에 도착했을 때 다시 pop, 하면서 빠지면 되기 때문

- 대신 네 방향 탐색을 진행하면서 방문한 부분은 T로 바꾸고, 다음 재귀때 다시는 방문하지 못하게 해야함

- 이렇게 재귀를 수행하면서 고정된 집의 위치이고, 거리가 K면 재귀 탈출 (이때,, 가짓수  +1 해줘야 함)

 

[Solution 코드]

n,m,k = map(int, input().split())
ary = []
sx, sy = n-1, 0 ## 항상 시작 좌표는 왼쪽 아래 라고 했음

for i in range(n):
    ary.append(list(map(str, input())))
    
dx = [0, 0, 1, -1]  ## 동, 서, 남, 북
dy = [1, -1, 0, 0]

stk = []
cnt = 0
def dfs(graph, x ,y, sol):
    global cnt
    
    #print(sol)
    
    if (x == 0 and y == m-1) and (len(sol) == k):
        cnt += 1
        return
    
    for i in range(len(dx)): ## 4방향 탐색
        nx = x + dx[i]
        ny = y + dy[i]
        
        if nx < 0 or nx >= n or ny < 0 or ny >= m or ary[nx][ny] == 'T': ## 자리 넘으면 안함, T면 안감
            continue
        
        sol.append((nx, ny))
        ary[nx][ny] = 'T'
        dfs(graph, nx, ny, sol)
        px, py = sol.pop()
        ary[px][py] = '.'
        
        
    
stk.append((sx, sy))
ary[sx][sy] = 'T' ## 초기 시작점 방문 여부도 확인해줘야함
dfs(ary, sx, sy, stk)
print(cnt)