https://www.acmicpc.net/problem/1189
나의 풀이
import sys
def _dfs(map_list, visit_info, now_R, now_C, now_dis, R, C, K):
answer = 0
if (now_dis <= K):
if ((now_R, now_C) == (0, C - 1)) and (now_dis == K):
return 1
else:
for m_R, m_C in ((1,0),(-1,0),(0,1),(0,-1)):
next_R, next_C = now_R + m_R, now_C + m_C
if (0 <= next_R < R) and (0 <= next_C < C) and (map_list[next_R][next_C] != 'T') and ((next_R, next_C) not in visit_info):
answer += _dfs(map_list, visit_info | {(next_R, next_C)}, next_R, next_C, now_dis + 1, R, C, K)
return answer
R, C, K = map(int, sys.stdin.readline().rstrip().split())
map_list = [list(sys.stdin.readline().rstrip()) for _ in range(R)]
print(_dfs(map_list, {(R - 1, 0)}, R - 1, 0, 1, R, C, K))
시간 복잡도
_dfs(map_list, visit_info, now_R, now_C, now_dis, R, C, K) : 각 트리에서 4방향을 탐색
해당 알고리즘 시간 복잡도 : 지수형 시간 복잡도 ( O( 4 ** K ) )
