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

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

17070번: 파이프 옮기기 1

파이썬이라 억까당함. 난이도는 낮지만 시간 초과로 고생했다.

밑에서부터 bfs(4), dfs(2), dp(1) 로 풀었다

맨 처음 bfs로 풀었을때 시간 초과가 채점 70%에서 자꾸 걸리길래 방법이 틀린 줄 알았다.

아마 파이썬이 아니였으면 맞았을 거 같다. 

from collections import deque
import sys

count = 0
N = int(input())
home = []
for _ in range(N):
    home.append([int(x) for x in sys.stdin.readline().rstrip().split()])

def bfs():
    global count
    deq = deque()
    deq.append([0,1,0]) # 0 가로 1 세로 2 대각선

    while deq:
        x, y, state = deq.popleft()
        if x == N - 1 and y == N - 1:
            count += 1
            continue

        if state == 0:
            if y == N - 1:
                continue

            if 0 <= x < N and 0 <= y + 1 < N and home[x][y + 1] == 0:
                deq.append([x, y + 1, 0])

            if 0 <= x + 1 < N and 0 <= y + 1 < N and home[x][y + 1] == 0 and home[x + 1][y] == 0 and home[x + 1][y + 1] == 0:
                deq.append([x + 1, y + 1, 2])

        elif state == 1:
            if x == N - 1:
                continue

            if 0 <= x + 1 < N and 0 <= y < N and home[x + 1][y] == 0:
                deq.append([x + 1, y, 1])

            if 0 <= x + 1 < N and 0 <= y + 1 < N and home[x][y + 1] == 0 and home[x + 1][y] == 0 and home[x + 1][y + 1] == 0:
                deq.append([x + 1, y + 1, 2])

        elif state == 2:

            if 0 <= x < N and 0 <= y + 1 < N and home[x][y + 1] == 0:
                deq.append([x, y + 1, 0])

            if 0 <= x + 1 < N and 0 <= y < N and home[x + 1][y] == 0:
                deq.append([x + 1, y, 1])

            if 0 <= x + 1 < N and 0 <= y + 1 < N and home[x][y + 1] == 0 and home[x + 1][y] == 0 and home[x + 1][y + 1] == 0:
                deq.append([x + 1, y + 1, 2])
                
bfs()
print(count)

방법은 간단하다. 탐색하면서 좌표와 같이 상태(가로, 세로, 대각선)를 나타내는 값도 큐에 넣어주면 된다.

근데 시간 초과떠서 설마 하고 dfs로 풀어봄.

 

import sys
count = 0
N = int(input())
home = []

for _ in range(N):
    home.append([int(x) for x in sys.stdin.readline().rstrip().split()])

def dfs(x,y,state): # state 0: 가로, 1: 세로 , 2: 대각선
    global count
    if x == N - 1 and y == N - 1:
        count += 1
        return

    if state == 0:
        if y == N - 1: # 이동불가
            return

        if 0 <= x < N and 0 <= y + 1 < N and home[x][y + 1] == 0:
            dfs(x, y + 1, 0)

        if 0 <= x + 1 < N and 0 <= y + 1 < N and home[x][y + 1] == 0 and home[x + 1][y] == 0 and home[x + 1][
            y + 1] == 0:
            dfs(x + 1, y + 1, 2)

    elif state == 1:
        if x == N - 1: # 이동불가
            return

        if 0 <= x + 1 < N and 0 <= y < N and home[x + 1][y] == 0:
            dfs(x + 1, y, 1)

        if 0 <= x + 1 < N and 0 <= y + 1 < N and home[x][y + 1] == 0 and home[x + 1][y] == 0 and home[x + 1][
            y + 1] == 0:
            dfs(x + 1, y + 1, 2)

    elif state == 2:
        if 0 <= x < N and 0 <= y + 1 < N and home[x][y + 1] == 0:
            dfs(x, y + 1, 0)

        if 0 <= x + 1 < N and 0 <= y < N and home[x + 1][y] == 0:
            dfs(x + 1, y, 1)

        if 0 <= x + 1 < N and 0 <= y + 1 < N and home[x][y + 1] == 0 and home[x + 1][y] == 0 and home[x + 1][
            y + 1] == 0:
            dfs(x + 1, y + 1, 2)

dfs(0,1,0)
print(count)

방법은 위에 bfs로 풀었던거랑 똑같다. 

근데 pypy로는 맞지만 python으로 채점하니 시간 초과가 떴다.

그냥 넘어가려다가 찜찜해서 찾아보니까 dp로도 해결가능해서 dp로 최종 해결했다.

 

풀이 과정

먼저 배열에 x, y 좌표와 가로, 세로, 대각선 상태를 저장하기 위해 3차원 리스트를 선언한다.

DP[0][0][1] = 1
for i in range(2,N):
    if home[0][i] == 0:
        DP[0][0][i] = DP[0][0][i - 1]

이후 초기값을 설정해준다. 1 행은 가로 리스트에만 입력해주면 된다.

중간에 1(벽)이 있으면 이후 값들은 0 이므로 벽을 만나기 전까지 1로 넣어준다.

 

for i in range(1,N):
    for j in range(1,N):
        if home[i][j] == 0 and home[i][j - 1] == 0 and home[i - 1][j] == 0:
            DP[2][i][j] = DP[0][i - 1][j - 1] + DP[1][i - 1][j - 1] + DP[2][i - 1][j - 1]
            # 대각선 파이프 놓기

        if home[i][j] == 0:
            DP[0][i][j] = DP[0][i][j - 1] + DP[2][i][j - 1]
            # 가로 파이프 놓기

            DP[1][i][j] = DP[1][i - 1][j] + DP[2][i - 1][j]
            # 세로 파이프 놓기

이후에는 조건에 맞게 DP리스트에 값을 넣어주면 된다. 백준 문제 설명에 있는 그림을 보면 도움된다.

 

전체 코드

import sys

home = []
N = int(input())
for _ in range(N):
    home.append([int(x) for x in sys.stdin.readline().rstrip().split()])

DP = [[[0 for _ in range(N)] for _ in range(N)] for _ in range(3)]
# 0 가로, 1 세로, 2 대각선

DP[0][0][1] = 1
for i in range(2,N):
    if home[0][i] == 0:
        DP[0][0][i] = DP[0][0][i - 1]
#print(DP)

for i in range(1,N):
    for j in range(1,N):
        if home[i][j] == 0 and home[i][j - 1] == 0 and home[i - 1][j] == 0:
            DP[2][i][j] = DP[0][i - 1][j - 1] + DP[1][i - 1][j - 1] + DP[2][i - 1][j - 1]
            # 대각선 파이프 놓기

        if home[i][j] == 0:
            DP[0][i][j] = DP[0][i][j - 1] + DP[2][i][j - 1]
            # 가로 파이프 놓기

            DP[1][i][j] = DP[1][i - 1][j] + DP[2][i - 1][j]
            # 세로 파이프 놓기
print(DP[0][N - 1][N - 1] + DP[1][N - 1][N - 1] + DP[2][N - 1][N - 1])

 

앞으로 시간 초과가 걸리면 bfs보단 dfs나 dp를 사용해 풀어야겠다.