February 11, 2023

17070번: 파이프 옮기기 1

문제 요약

• N x N 격자판에서 파이프를 옮길 수 있는 경우의 수가 다음과 같을 때 (N, N)까지 파이프를 옮길 수 있는 경우의 수 출력 (색상으로 표시된 칸은 빈칸이어야 한다.)

  

• 제한 시간 : 1초

문제 풀이

from sys import stdin

input = stdin.readline
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
count = 0

VERTICAL = 0
HORIZONTAL = 1
DIAGONAL = 2

def dfs(row, col, type):
    global count

    if ((row, col) == (N - 1, N - 1)):
        count += 1
        return

    if ((type == DIAGONAL or type == HORIZONTAL) and col + 1 < N):
        if (board[row][col + 1] == 0):
            dfs(row, col + 1, HORIZONTAL)

    if ((type == VERTICAL or type == DIAGONAL) and row + 1 < N):
        if (board[row + 1][col] == 0):
            dfs(row + 1, col, VERTICAL)

    if (row + 1 < N and col + 1 < N):
        if (board[row + 1][col + 1] == 0 and board[row + 1][col] == 0 and board[row][col + 1] == 0):
            dfs(row + 1, col + 1, DIAGONAL)

dfs(0, 1, HORIZONTAL)

print(count)

• DFS를 이용한 완전탐색
• DP를 이용한 풀이도 가능