[Python]17070. 파이프 옮기기1

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

17070번: 파이프 옮기기 1

---

 

처음엔 DFS형태로 check배열 생성한다음 모든 경로를 다 탐색했으나..

계속 60% 쯤에서 계속 시간초과가 발생했다.

다시 생각해보니 굳이 방문확인을 안해도, if문 조건 분기에 의해 가능한 모든 경우를 탐색하므로 가볍게 풀 수 있다.

 

 

def recur(curr_y,curr_x, pipe_type):
    global n, answer
 
    if (curr_y, curr_x) == (n-1, n-1):
        answer += 1
        return
 
    else:
        if pipe_type == 0:
            if curr_x+1 < n and MAP[curr_y][curr_x+1] == '0':
                recur(curr_y, curr_x+1, 0)
 
            if curr_y+1 < n and curr_x+1 < n and MAP[curr_y][curr_x+1] == '0' and MAP[curr_y+1][curr_x+1] == '0' and MAP[curr_y+1][curr_x] == '0':
                recur(curr_y+1, curr_x+1, 1)
 
        elif pipe_type == 1:
            if curr_x + 1 < n and MAP[curr_y][curr_x + 1] == '0':
                recur(curr_y, curr_x + 1, 0)
 
            if curr_y + 1 < n and curr_x + 1 < n and MAP[curr_y][curr_x + 1] == '0' and MAP[curr_y + 1][
                curr_x + 1] == '0' and MAP[curr_y + 1][curr_x] == '0':
                recur(curr_y + 1, curr_x + 1, 1)
 
            if curr_y + 1 < n and MAP[curr_y+1][curr_x] == '0':
                recur(curr_y+1, curr_x, 2)
 
        elif pipe_type == 2:
            if curr_y + 1 < n and curr_x + 1 < n and MAP[curr_y][curr_x + 1] == '0' and MAP[curr_y + 1][
                curr_x + 1] == '0' and MAP[curr_y + 1][curr_x] == '0':
                recur(curr_y + 1, curr_x + 1, 1)
 
            if curr_y + 1 < n and MAP[curr_y+1][curr_x] == '0':
                recur(curr_y+1, curr_x, 2)
 
n = int(input())
MAP = [input().split() for _ in range(n)]
answer = 0
recur(0,1,0)
print(answer)