[BOJ][python] 17070. 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

---

💡IDEA

DFS를 사용하는 문제이다.

행, 열, 파이프 방향 세 변수를 사용하여 DFS를 수행한다. 파이프 방향은 0이 가로, 1이 세로, 2가 대각선이다.

다음 파이프가 가로로 갈 수 있는 경우는 현재 파이프가 가로 혹은 대각선 인 경우이다.

가로로 가기 위해서는 다음 열 값이 범위 내에 있고, 빈 칸(0)이어야 한다.

다음 파이프가 세로로 갈 수 있는 경우는 현재 파이프가 세로 혹은 대각선인 경우이다.

세로로 가기 위해서는 다음 행 값이 범위 내에 있고, 빈 칸(0)이어야 한다.

다음 파이프가 대각선으로 갈 수 있는 경우는 현재 파이프가 가로 혹은 세로 혹은 대각선, 즉 어떤 경우든 상관 없다.

대각선으로 가기 위해서는 다음 행, 다음 열 값이 범위 내에 있고, 빈 칸(0)이어야 한다.

DFS를 수행하고 (N-1, N-1) 칸에 도착한다면 카운트를 세어주고 돌아간다.

 

📌CODE

import sys
input = sys.stdin.readline

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

def dfs(x, y, z):
    global cnt
    if x == N-1 and y == N-1:
        cnt += 1
        return
    if z == 0 or z == 2:
        if y+1 < N and home[x][y+1] == 0:
            dfs(x, y+1, 0)
    if z == 1 or z == 2:
        if x+1 < N and home[x+1][y] == 0:
            dfs(x+1, y, 1)
    if x+1 < N and y+1 < N and home[x][y+1] == 0 and home[x+1][y] == 0 and home[x+1][y+1] == 0:
        dfs(x+1, y+1, 2)

cnt = 0
dfs(0, 1, 0)
print(cnt)