파이프 옮기기 1 ( 17070번 )

17070번: 파이프 옮기기 1

 

나의 풀이

import sys

"""
p_type : 1 >>> 가로
p_type : 2 >>> 세로
p_type : 3 >>> 대각선

"""
def _dfs(x, y, p_type):
    global answer
    if (x == (n - 1)) and (y == (n - 1)):
        answer += 1
        return

    if (0 <= x + 1 < n) and (0 <= y + 1 < n) and (map_list[x][y+1] == 0) and (map_list[x+1][y] == 0) and (map_list[x+1][y+1] == 0):
        _dfs(x+1, y+1, 3)
    if ((p_type == 1) or (p_type == 3)) and (0 <= y + 1 < n) and (map_list[x][y+1] == 0):
        _dfs(x, y+1, 1)
    if ((p_type == 2) or (p_type == 3)) and (0 <= x + 1 < n) and (map_list[x+1][y] == 0):
        _dfs(x+1, y, 2)

n = int(sys.stdin.readline())
map_list = [tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

answer = 0
_dfs(0, 1, 1)
print(answer)

 

시간 복잡도

_dfs(x, y, p_type) : 이차형 맵을 탐색하며 조건 만족시 answer 증감
- 매 탐색시 최대 3개의 재귀 호출

해당 알고리즘 시간 복잡도 : 지수 시간 복잡도 ( O(3 ** (n**2)) )