BOJ - 1189

백준 문제 링크
컴백홈

❓접근법

1. DFS를 사용했다.
2. 백트래킹 알고리즘을 사용함 (해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가는 알고리즘)
3. 좌표가 집의 좌표일 때, 거리가 K와 같다면 answer + 1
4. <핵심 부분>
   갈 수 있는 곳을 탐색하면서,
   visited[nx][ny] = True로 방문 처리
   dfs(nx,ny, distance + 1) 실행
   visited[nx][ny] = False로 방문 처리를 초기화
5. dfs(start_x, start_y, 1) 실행 후 answer 출력하면 끝

R,C,K = map(int, input().split())
lst = []
for i in range(R):
    lst.append(list(input()))
    
visited = [[False] * C for _ in range(R)]
visited[R-1][0] = True

start_x, start_y = R-1,0
end_x, end_y = 0, C-1

answer = 0

def dfs(x,y, distance):
    
    
    if (x,y) == (end_x,end_y):
        if distance == K:
            global answer
            answer += 1
        return 
    
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        
        if (0<=nx<R) and (0<=ny<C) and (lst[nx][ny] != 'T') and (not visited[nx][ny]):
            visited[nx][ny] = True
            dfs(nx,ny, distance + 1)
            visited[nx][ny] = False
            
dfs(start_x, start_y, 1)
print(answer)

오랜만에 DFS방식을 사용해서 어려웠고, 백트래킹 방법이 생소해서 좀 어려웠다.