파이프 옮기기 1

처음 생각했던 아이디어

• 가로,세로,대각선 정보에 따라 다음에 갈 수 있는 곳을 다시 각각 가로,세로,대각선 함수를 이용하여 해결하려고 했음
  • 0%에서 시간 초과 발생

그 다음 생각했던 아이디어

• 이미 들어온 곳에 다른 경로나 막대 방향으로 들어온다면 원래 있던 가짓 수에서 들어온 가짓 수를 더하면 된다고 생각
  • 들어올때의 막대 방향에 따라 갈 수 있는 경우의 수가 모두 다르므로 불가능

개선한 아이디어

• 가로,세로,대각선 함수를 각각 만드는 것이 아니라 bfs 함수 하나만을 이용하여 탐색한다.

• 가능한 방향에는 deque에 y,x뿐만 아니라 방향 정보도 넣어줌

• 넣어준 방향에 따라 다시 갈 수 있는 방향 탐색

• 도착지점에 도착하면 갯수 + 1

• 시간 초과 0%

개선한 아이디어(2)

• 위 bfs를 재귀함수를 이용한 dfs로 바꿔줌
• 통과

결론

• deque를 이용하더라도 bfs보다는 재귀의 dfs가 빠름

코드

• python

def dfs(y,x,shape):
    global cnt
    if y == N-1 and x == N-1:
        cnt += 1
        return
    if shape == 0:
        if x + 1 < N and not matrix[y][x+1]:
            dfs(y,x+1,0)
        if y + 1 < N and x + 1 < N and not matrix[y+1][x+1] and not matrix[y][x+1] and not matrix[y+1][x]:
            dfs(y+1,x+1,2)
    elif shape == 1:
        if y + 1 < N and not matrix[y+1][x]:
            dfs(y+1,x,1)
        if y + 1 < N and x + 1 < N and not matrix[y+1][x+1] and not matrix[y][x+1] and not matrix[y+1][x]:
            dfs(y+1,x+1,2)
    elif shape == 2 :
        if x + 1 < N and not matrix[y][x+1]:
           dfs(y,x+1,0)
        if y + 1 < N and not matrix[y+1][x]:
           dfs(y+1,x,1)
        if y + 1 < N and x + 1 < N and not matrix[y+1][x+1] and not matrix[y][x+1] and not matrix[y+1][x]:
           dfs(y+1,x+1,2)


N = int(input())
matrix = [list(map(int,input().split())) for _ in range(N)]
cnt = 0
dfs(0,1,0)
print(cnt)