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

17070번 - 파이프 옮기기 1

 

처음 보고 BFS로 풀리겠거니~ 해서 그냥 BFS로 질렀다. 빠르게 작성하고 테스트 케이스도 잘 돌아가서 빠르게 제출했다.

 

내 코드(BFS,시간 초과):

# dawitblog.tistory.com/146
from sys import stdin
from collections import deque
input = stdin.readline

# 입력
n = int(input())
mat = []
for _ in range(n):
    mat.append(list(map(int,input().split())))

# (r,c,status) status는 0 -> 가로 , 1 -> 세로 , 2 -> 대각선
q = deque([(0,1,0)])
# 경우의 수 변수
count = 0
while q:
    r,c,status = q.popleft()

    # 목적지 도달
    if r == c == n-1:
        count += 1
        continue

    # 대각선 이동 가능 여부 확인
    if c+1 < n and r+1 < n and mat[r][c+1] + mat[r+1][c] + mat[r+1][c+1] == 0:
        # 대각선 이동
        q.append((r+1,c+1,2))
    # 가로 상태라면
    if status == 0:
        # 가로 이동 가능 여부 확인
        if c+1 < n and mat[r][c+1] != 1:
            q.append((r,c+1,0))
    # 세로 상태라면
    elif status == 1:
        # 세로 이동 가능 여부 확인
        if r+1 < n and mat[r+1][c] != 1:
            q.append((r+1,c,1))
    # 대각선 상태라면
    elif status == 2:
        # 가로, 세로 이동 가능 여부 확인
        if c+1 < n and mat[r][c+1] != 1:
            q.append((r,c+1,0))
        if r+1 < n and mat[r+1][c] != 1:
            q.append((r+1,c,1))

# 출력
print(count)

 

쉽게쉽게 넘어갈 수 있을줄 알았지만... 시간 초과의 벽에 부딪히고 다른 방법을 찾아야 했다. 딱히 다른 방법이 생각나지 않아서 DP겠구나! 라고 생각했고 DP로 구현하기로 했다.

 

처음에는 2중 리스트를 사용하여 풀려고 했지만 가로로 갈때 조건 검사가 너무 까다로워서 3중 리스트로 풀었다.

 

내 코드:

# dawitblog.tistory.com/146
from sys import stdin
input = stdin.readline

# 입력
n = int(input())
dp = [[[0,0,0] for _ in range(n)] for _ in range(n)]
walls = [False]*(n*n)
# 벽 정보 입력
for r in range(n):
    l = list(map(int,input().split()))
    for c in range(n):
        if l[c] == 1:
            walls[r*n+c] = True

dp[0][1][0] = 1
for r in range(n):
    for c in range(2,n):
        if not walls[r*n+c]:
            # 가로 확인
            dp[r][c][0] += dp[r][c-1][0] + dp[r][c][0] + dp[r][c-1][2]

            if r:
                # 세로 확인
                dp[r][c][1] += dp[r-1][c][1] + dp[r-1][c][2]

                # 대각선 확인
                if not walls[r*n+c-1] and not walls[(r-1)*n+c]:
                    dp[r][c][2] += dp[r-1][c-1][0] + dp[r-1][c-1][1] + dp[r-1][c-1][2]
                
#출력
print(sum(dp[n-1][n-1]))

 

아까 BFS로 풀었을 때와 비슷하게 0은 가로, 1은 세로, 2는 대각선을 의미한다.

 

column같은 경우 2부터 검사하면 된다. 이는 시작 조건이 가로로 놓여 있기 때문에 column의 0 과 1은 이동가능한 방향을 봤을 때 절대로 갈 수 없는 곳이다.