[백준 17070번] 파이프 옮기기1

17070번: 파이프 옮기기 1

n = int(input())

house = [list(map(int,input().split())) for _ in range(n)]
visited = [[False]*n for _ in range(n)]

dx_r, dy_r = [0,1], [1,1] # 가로일 경우 움직일 수 있는 방향
dx_c, dy_c = [1,1], [0,1] # 세로일 경우 움직일 수 있는 방향
dx_d, dy_d = [0,1,1], [1,0,1] # 대각선일 경우 움직일 수 있는 방향

answer = 0

def dfs(x,y,direction):
    # visited[x][y] = True

    global answer

    if x == n-1 and y == n-1:
        answer += 1
        return

    if direction == "row":

        if 0 <= y+1 < n and house[x][y+1] == 0:
            dfs(x,y+1,"row")
        if 0 <= x+1 < n and 0 <= y+1 < n and house[x][y+1] == 0 and house[x+1][y] == 0 and house[x+1][y+1] == 0:
            dfs(x+1,y+1,"dig")

    elif direction == "col":
        if 0 <= x+1 < n and house[x+1][y] == 0:
            dfs(x+1,y,"col")
        if 0 <= x+1 < n and 0 <= y+1 < n and house[x][y+1] == 0 and house[x+1][y] == 0 and house[x+1][y+1] == 0:
            dfs(x+1,y+1,"dig")

    elif direction == "dig":
        if 0 <= y+1 < n and house[x][y+1] == 0:
            dfs(x,y+1,"row")
        if 0 <= x+1 < n and house[x+1][y] == 0:
            dfs(x+1,y,"col")
        if 0 <= x+1 < n and 0 <= y+1 < n and house[x][y+1] == 0 and house[x+1][y] == 0 and house[x+1][y+1] == 0:
            dfs(x+1,y+1,"dig")   

dfs(0,1,"row")

print(answer)

이번 문제는 조건에 맞게 파이프를 이동시켜가며 (n-1, n-1) 좌표에 도달하는 경우의 수를 구하는 문제이다.

 

처음에 이 문제를 접근했을 땐 DFS와 Backtracking을 사용하여 문제를 풀었었는데, pypy3 로만 통과가 되고 python3로는 시간초과가 발생하였다.

 

이 문제를 완벽하게 풀이하려면 DP를 사용하여야 한다고 하는데, 추후에 DP를 활용하여 다시 문제를 풀어보려고 한다.