[백준 17070번] - 파이프 옮기기 1 (Python)

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

 

 

 

 

 

 

 

 

 

# BFS풀이과정

1. 제한시간은 1초, bfs를 이용하여도 N의 크기가 그렇게 크지 않기에 BFS를 이용

2-1. 파이프는 가로상태에서 가로, 대각선방향으로 밀 수 있음

2-2. 세로상태에서는 세로, 대각선으로 밀 수 있음

2-3. 대각선 상태에서는 모든 방향으로 밀 수 있음

3. 각각의 방식대로 밀고 나서의 파이프의 상태, 행, 열을 튜플로 묶어서 큐에 저장

4. 만약 행,열이 모두 N이 된다면 카운트를 1증가시킴

5. 최종 카운트를 출력

 

***주의점***

대각선으로 밀 때는 오른쪽, 대각선아래, 아래, 총 3개의 칸에 전부 벽이 없어야함 

 

위와 같은 생각으로 BFS를 이용하여 코드를 짰다.

 

 

[BFS를 이용한 코드 - 시간초과]

# ex_17070
import sys
from collections import deque
N = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
cnt = 0
def bfs():
    global cnt
    q = deque([('r',1,2)])
    while q:
        (state,x,y) = q.popleft()
        if x == N and y == N:
            cnt += 1
            continue
        rx,ry = x,y+1
        dx,dy = x+1,y
        cx,cy = x+1,y+1
        # 가로일때
        if state == 'r':
            if ry <= N: # 가로로 밀기
                if graph[rx-1][ry-1] == 0:
                    q.append(('r',rx,ry))
            if cx <= N and cy <= N: # 대각선으로 밀기
                if graph[cx-1][y-1] == 0 and graph[x-1][cy-1] == 0 and graph[cx-1][cy-1] == 0:
                    q.append(('c',cx,cy))
        # 세로일때
        elif state == 'd':
            if dx <= N: # 세로로 밀기
                if graph[dx-1][dy-1] == 0:
                    q.append(('d',dx,dy))
                if cx <= N and cy <= N: # 대각선으로 밀기
                    if graph[cx-1][y-1] == 0 and graph[x-1][cy-1] == 0 and graph[cx-1][cy-1] == 0:
                        q.append(('c',cx,cy))
        # 대각선일때
        else:
            if ry <= N: # 가로로 밀기
                if graph[rx-1][ry-1] == 0:
                    q.append(('r',rx,ry))
            if dx <= N: # 세로로 밀기
                if graph[dx-1][dy-1] == 0:
                    q.append(('d',dx,dy))
            if cx <= N and cy <= N: # 대각선으로 밀기
                if graph[cx-1][y-1] == 0 and graph[x-1][cy-1] == 0 and graph[cx-1][cy-1] == 0:
                    q.append(('c',cx,cy))                         
bfs()
print(cnt)

 

bfs로는 시간초과가 발생했다....

그래서 다음으로는 dp를 이용하여 풀어보았다.

 

 

# DP풀이과정

1. BFS에서는 밀기 전의 각 상태별로 어떻게 밀 수 있는지를 고려했다면,

DP에서는 밀고 나서의 각 상태별로 전칸에 어떻게 밀 수 있었는지의 경우의 수를 고려

2. (N+1) x (N+1) 크기의 2차원 배열을 만들고, 배열의 각 요소는 [가로,세로,대각선]의 배열

(결과적으로 보면 3차원 배열의 형태)

3. dp[1][1]부터 dp[N][N]을 순회하면서 채워나감

4. dp[N][N]의 가로, 세로, 대각선 3개의 요소를 더한값을 출력

 

 

 

[DP를 이용한 코드 - 성공] 

# ex_17070
import sys
N = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dp = [[[0,0,0] for _ in range(N+1)] for _ in range(N+1)] # [가로,세로,대각선]

# dp
def sol():
    for i in range(1,N+1):
        for j in range(1,N+1):
        
            # 시작지점
            if i == 1 and j == 2:
                dp[i][j][0] = 1
                continue
                
            # 벽이 없는지 확인
            if graph[i-1][j-1] == 0:
                # 가로
                dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2]
                # 세로
                dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2]
                # 대각선(추가적인 벽의 유무 확인 필요)
                if graph[i-2][j-1] == 0 and graph[i-1][j-2] == 0:
                    dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2]
    
sol()
print(sum(dp[N][N]))

 

 

N의 범위의 최대값이 크지 않기에 DP를 이용하는것이 시간이 더 적게 걸리는것 같다.

시간복잡도를 항상 잘 비교하고 문제를 해결하려는 습관을 길러야겠다.