[백준] 17070: 파이프 옮기기 1 (Python)

문제

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

접근방법

1. BFS 로 모든 파이프로 완전 탐색 : 시간초과 63%
2. DFS 로 이미 성공한 경로에 접근하면 재귀 종료 : 시간초과 70%
3. DP 3차원 배열을 통해서 파이프 모양에 따라 저장 : 통과

DP풀이

"""
typ
0 : -
1 : \
2 : |
"""

dd = (
    (0,1),(1,1),(1,0)
)
dr = (0,-1,-1)
dc = (-1,-1,0)
pipe_type = ((0,1),(0,1,2),(1,2))

N = int(input())
world = [list(map(int,input().split())) for _ in range(N)]

dp = [[[0,0,0] for _ in range(N)] for _ in range(N)]
dp[0][1][0] = 1
for r in range(N):
    for c in range(2,N):
        if world[r][c]:
            continue
        for i in [0,2]:
            dp[r][c][i] = sum(dp[r+dr[i]][c+dc[i]][j] for j in pipe_type[i])
        if not(world[r-1][c] or world[r][c-1]): # 둘다 벽이 아니면
            dp[r][c][1] = sum(dp[r+dr[1]][c+dc[1]][j] for j in pipe_type[1])
            

# print(*dp,sep='\n',end='\n\n')
print(sum(dp[N-1][N-1]))
exit()

check = [[[False,False,False] for _ in range(N)] for _ in range(N)]

if world[N-1][N-1] == 1:
    print(0)
    exit()
 
cnt = 0

DFS(0,1,0)

# print(*check,sep='\n',end='\n\n')
print(cnt)

BFS

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

dd = (
    (0,1),(1,1),(1,0)
)
def pipe(r,c,typ):
    if typ == 0:
        for i in [0,1]:
            dr = dd[i][0]
            dc = dd[i][1]
            if not(0 <= r + dr < N and 0 <= c + dc < N):
                continue
            if world[r+dr][c+dc] != 1:
                if i == 1:
                    if world[r+1][c] != 1 and world[r][c+1] != 1:
                        check[r+dr][c+dc] += 1
                        que.append((r+dr,c+dc,i))
                        continue
                    else:
                        continue
                check[r+dr][c+dc] += 1
                que.append((r+dr,c+dc,i))
            
    elif typ == 1:
        for i in [1,0,2]:
            dr = dd[i][0]
            dc = dd[i][1]
            if not(0 <= r + dr < N and 0 <= c + dc < N):
                continue
            if world[r+dr][c+dc] != 1:
                if i == 1:
                    if world[r+1][c] != 1 and world[r][c+1] != 1:
                        check[r+dr][c+dc] += 1
                        que.append((r+dr,c+dc,i))
                        continue
                    else:
                        continue
                check[r+dr][c+dc] += 1
                que.append((r+dr,c+dc,i))
            
    elif typ == 2:
        for i in [2,1]:
            dr = dd[i][0]
            dc = dd[i][1]
            if not(0 <= r + dr < N and 0 <= c + dc < N):
                continue
            if world[r+dr][c+dc] != 1:
                if i == 1:
                    if world[r+1][c] != 1 and world[r][c+1] != 1:
                        check[r+dr][c+dc] += 1
                        que.append((r+dr,c+dc,i))
                        continue
                    else:
                        continue
                check[r+dr][c+dc] += 1
                que.append((r+dr,c+dc,i))
                
                
N = int(input())
world = [list(map(int,input().split())) for _ in range(N)]
check = [[0]*N for _ in range(N)]
que = deque()
que.append((0,1,0))
check[0][0] = 1
check[0][1] = 1

while que:
    pipe(*que.popleft())
print(check[N-1][N-1])

DFS

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

dd = (
    (0,1),(1,1),(1,0)
)

pipe_type = ((0,1),(0,1,2),(1,2))

def DFS(r,c,typ):
    global cnt
        
    if r == N-1 and c == N-1: # 골인지점이면
        cnt += 1
        check[r][c][typ] = True # 골갈수있음
        return True
        
    for i in pipe_type[typ]:
        dr = dd[i][0]
        dc = dd[i][1]
        
        if not(0 <= r + dr < N and 0 <= c + dc < N): # 범위안이고
            continue
        
        if world[r+dr][c+dc] == 1: # 벽이 아닐때
            continue
        
        if i == 1: # 대각일때 3칸차지
            if not(world[r+dr][c] != 1 and world[r][c+dc] != 1): # 3칸 차지 못하면
                continue # 넘기기
            
        if check[r+dr][c+dc][i] == True: # 가려는 곳이 골지점으로 이어져 있으면
            # 안가도 돼
            cnt += 1
        # 아니면 가봐
        elif DFS(r+dr,c+dc,i): # 골인지점을 만나고 돌아오는길
            check[r+dr][c+dc][i] = True # 골갈수있음
            

N = int(input())
world = [list(map(int,input().split())) for _ in range(N)]
check = [[[False,False,False] for _ in range(N)] for _ in range(N)]

if world[N-1][N-1] == 1:
    print(0)
    exit()
 
cnt = 0

DFS(0,1,0)

print(cnt)