BOJ 17070 파이프 옮기기 1(python 3)

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

 

파이프 옮기기 1의 코드는 시간 제한 때문에 pypy3으로 제출해야합니다.

 

 

main함수는 이렇습니다.

n = int(input())
D = [[*map(int, input().split())] for _ in range(n)]
k = 0
dfs(0, 1, 0)
print(k)

dfs함수는 이렇습니다.

def dfs(x, y, z):# → 0, ↘ 1, ↓ 2
    global k
    if x == n - 1 and y == n - 1: k += 1
    if z == 0 or z == 1: #파이프 방향 확인
        if y + 1 < n: # 맵을 넘지 못하게 설정
            if D[x][y + 1] == 0: # 칸에 벽이 없는지 확인
                dfs(x, y + 1, 0)
    if z == 0 or z == 1 or z == 2:
        if x + 1 < n and y + 1 < n:
            if D[x + 1][y] == D[x][y + 1] == D[x + 1][y + 1] == 0:
                dfs(x + 1, y + 1, 1)
    if z == 1 or z == 2:
        if x + 1 < n:
            if D[x + 1][y] == 0:
                dfs(x + 1, y, 2)

dfs함수에서 x,y,z인자를 받는데요.

x,y는 좌표이고, z는 파이프의 방향을 숫자로 표현하였습니다.(z = → 0, ↘ 1, ↓ 2)

문제에서 요구한대로 칸이 색칠되어 있는 곳은 벽이 없어야 파이프를 이동할 수 있게 하였습니다.

 

 

 

 

 

이렇게 해서 완성된 코드입니다.

def dfs(x, y, z):# → 0, ↘ 1, ↓ 2
    global k
    if x == n - 1 and y == n - 1: k += 1
    if z == 0 or z == 1: #파이프 방향 확인
        if y + 1 < n: # 맵을 넘지 못하게 설정
            if D[x][y + 1] == 0: # 칸에 벽이 없는지 확인
                dfs(x, y + 1, 0)
    if z == 0 or z == 1 or z == 2:
        if x + 1 < n and y + 1 < n:
            if D[x + 1][y] == D[x][y + 1] == D[x + 1][y + 1] == 0:
                dfs(x + 1, y + 1, 1)
    if z == 1 or z == 2:
        if x + 1 < n:
            if D[x + 1][y] == 0:
                dfs(x + 1, y, 2)
 
n = int(input())
D = [[*map(int, input().split())] for _ in range(n)]
k = 0
dfs(0, 1, 0)
print(k)