[백준 BOJ] 17070 파이프 옮기기 1 (python)

문제 출처 : https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

 

dfs문제처럼 생겨서 바로 도전해보았으나 시간초과로 실패!
pypy로는 정답이 나왔지만 너무 느려서
문제 분류를 보고 dp로 재도전했습니다.

 

🔥 DFS 코드 (시간 초과)

def sol(i, j, flag):
    global cnt
    # 끝에 도착하면 결과값 1 증가
    if i == N-1 and j == N-1:
        cnt += 1
        return

    # 가로 세로 끝 부분에서 더 이상 못 가는 상태라면 종료
    elif i == N-1 and flag == 1:
        return
    elif j == N-1 and flag == 0:
        return

    # 전진
    else:
        # 가로 : 가로 and 대각선 이동
        if flag == 0:
            if j+1 < N and arr[i][j+1] == 0:
                sol(i, j+1, 0)
            if i+1 < N and j+1 < N and arr[i+1][j+1] == 0 and arr[i][j+1] == 0 and arr[i+1][j] == 0:
                sol(i+1, j+1, 2)

        # 세로 : 세로 and 대각선 이동
        elif flag == 1:
            if i+1 < N and arr[i+1][j] == 0:
                sol(i+1, j, 1)
            if i+1 < N and j+1 < N and arr[i+1][j+1] == 0 and arr[i][j+1] == 0 and arr[i+1][j] == 0:
                sol(i+1, j+1, 2)

        # 대각선 : 가로 amd 세로 and 대각선 이동
        else:
            if j+1 < N and arr[i][j+1] == 0:
                sol(i, j+1, 0)
            if i+1 < N and arr[i+1][j] == 0:
                sol(i+1, j, 1)
            if i+1 < N and j+1 < N and arr[i+1][j+1] == 0 and arr[i][j+1] == 0 and arr[i+1][j] == 0:
                sol(i+1, j+1, 2)
        return

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

# 첫 시작
flag = 0
i = 0
j = 1
cnt = 0
if arr[N-1][N-1]:
    print(cnt)
else:
    sol(i, j, flag)
    print(cnt)

⭕ 해설

1. dfs를 이용하여 모든 경로를 구하고 N-1, N-1 지점에 도착할 경우 cnt에 1을 더해주었습니다.
2. flag를 이용해 이전 모습이 가로, 세로, 대각선임을 나타내었습니다.
   • 가로에서 왔다면 가로or 대각선 이동 가능
   • 세로에서 왔다면 세로or대각선 이동 가능
   • 대각선에서 왔다면 가로or세로or대각선 이동 가능

 

🔥 DP 코드 (통과)

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

# 가로, 세로, 대각선 각각 계산
dp1 = [[0 for _ in range(N)] for _ in range(N)]
dp2 = [[0 for _ in range(N)] for _ in range(N)]
dp3 = [[0 for _ in range(N)] for _ in range(N)]

# 첫 시작 (0,1) => 가로 1개 저장
dp1[0][1] = 1

# dp에 값 저장
for i in range(0, N):
    for j in range(2, N):
    	# 갈 수 잇는 곳이라면
        if arr[i][j] == 0:
        	# 세 곳 다 가능한 경우 1,2,3 모두 갱신
            if 0 <= i-1 and 0 <= j-1 and arr[i-1][j] == 0 and arr[i][j-1] == 0:
                dp1[i][j] = dp1[i][j-1] + dp3[i][j-1]
                dp2[i][j] = dp2[i-1][j] + dp3[i-1][j]
                dp3[i][j] = dp1[i-1][j-1] + dp2[i-1][j-1] + dp3[i-1][j-1]
                
            # 가로 : 왼쪽 칸에서 가로, 대각선에서 가로로 오는 경우
            # 세로 : 위 칸에서 가로, 대각선에서 세로로 오는 경우
            # 대각선 : 왼쪽 위 칸에서 가로, 세로, 대각선으로 오는 경우


			# 대각선이 불가능한 경우 1,2만 갱신
            else:
                if 0 <= i-1:
                    dp2[i][j] = dp2[i-1][j] + dp3[i-1][j]
                if 0 <= j-1:
                    dp1[i][j] = dp1[i][j-1] + dp3[i][j-1]

result = dp1[N-1][N-1] + dp2[N-1][N-1] + dp3[N-1][N-1]
print(result)

⭕ 해설

1.  가로, 세로, 대각선의 경우를 나누어 dp에 값을 저장했습니다.
2.  파이프의 끝 점을 기준으로 잡았습니다.
3.  첫 위치는 가로이며 끝 지점이 0,1이므로 dp[0][1]에 1을 저장합니다.
4.  현재 위치가 가로,세로,대각선으로 존재 가능하다면 다음과 같은 규칙으로 dp에 저장합니다. 
   •  현재 위치에서 가로라면 이 전 위치는 한 칸 왼쪽이고, 그 때의 모습은 가로, 대각선인 경우
   •  세로라면 이 전 위치는 한 칸 위쪽이고, 그 때의 모습은 세로, 대각선인 경우
   •  대각선이라면 이 전 위치는 왼쪽 위이고, 그 때의 모습은 가로, 세로, 대각선의 경우
5. dp에 값을 저장한 다음 도착지에 저장된 값을 모두 더해주어 답을 구해줍니다.

 

---

DFS 문제

2022.02.25 - [Algorithm/SWEA] - [SWEA] [파이썬 S/W 문제해결 기본] 6일차 - 미로의 거리 (python)

[SWEA] [파이썬 S/W 문제해결 기본] 6일차 - 미로의 거리 (python)

---

DP 문제

2022.02.18 - [Algorithm/SWEA] - [SWEA 4613] 러시아 국기 같은 깃발 (python)

[SWEA 4613] 러시아 국기 같은 깃발 (python)

2022.02.18 - [Algorithm/BAEKJOON] - [백준 BOJ] 13398 연속합 2 (python)

[백준 BOJ] 13398 연속합 2 (python)