[백준 17070번] 파이썬 - 파이프

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

17070번: 파이프 옮기기 1

 

 

# 조건

• 새 집의 크기는 N x N 격자판으로 나타낼 수 있고, 1 x 1 크기의 정사각형 칸으로 나누어져 있다.
• 각각의 칸은 (r, c)로 나타낼 수 있고 r은 행의 번호, c는 열의 번호이며 행과 열의 번호는 1부터 시작한다.
• 파이프는 아래와 같은 형태이고 2칸을 차지한다.

 

• 파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.

 

• 파이프는 빈 칸만 차지할 수 있으며 회전은 45도로만 가능하다.
• 즉 가로로 놓여진 파이프에는 대각선 아래와 가로 방향만 놓을 수 있고,
• 세로의 경우 대각선 아래와 세로로만,
• 대각선의 경우 대각선 세로 가로 모두 회전 가능하다.
  이 때, 대각선의 경우 아래와 같이 3칸이 비어있어야 파이프를 놓을 수 있다.

 

• 가장 처음에는 (1,1)과 (1,2)를 차지하고 있고, 방향은 가로 일 때, 파이프의 한 쪽 끝을 (N, N)으로 이동시키는 방법의 개수를 구하자

 

# 접근 방법

• BFS를 이용하여 풀어주면 될 것 같다.
• 파이프의 종류를 1,2,3으로 기록해주고 각 파이프에 맞는 범위를 체크해준다.
• 가로인 경우 -> 가로 파이프가 가능하다면 대각 체크
• 세로인 경우 -> 세로 파이프가 가능하다면 대각 체크
• 대각인 경우 -> 세로와 가로 파이프가 모두 가능하다면 대각 체크
• 가능하다면 DEQUE에 넣어주고 (N, N) 에 도착하였다면 결과 + 1
• 시간초과 -- 따라서 dp로 풀어주었다 

 

bfs로 풀이 시 시간초과

• 동일한 로직의 dfs로 풀이시 통과코드가 꽤 있었다 하지만 dfs보단 dp로 풀어보았다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  
  
def bfs(t):  
    arr = t  
    result = 0  
    q = deque()  
    q.append((0,1,1))  
    while q:  
        sti, stj, type = q.popleft()  
        # visited[sti][stj] = 1  
        if sti == N-1 and stj == N-1:  
            result += 1  
  
        if type == 1:  
            ni, nj = sti, stj+1  
            if 0<=ni<=N-1 and 0<=nj<=N-1 and arr[ni][nj] == 0:  
                q.append((ni,nj,1))  
                for i, j in garo:  
                    ni, nj = sti+i, stj + j  
                    if not (0 <= ni <= N - 1 and 0 <= nj <= N - 1 and arr[ni][nj] == 0):  
                        break  
                else:  
                    q.append((ni, nj, 3))  
  
        elif type == 2:  
            ni, nj = sti+1, stj  
            if 0<=ni<=N-1 and 0<=nj<=N-1 and arr[ni][nj] == 0:  
                q.append((ni,nj,2))  
                for i, j in sero:  
                    ni, nj = sti+i, stj + j  
                    if not (0 <= ni <= N - 1 and 0 <= nj <= N - 1 and arr[ni][nj] == 0):  
                        break  
                else:  
                    q.append((ni, nj, 3))  
  
        elif type == 3:  
            cnt = 0  
            ni, nj = sti+1, stj  
            if 0<=ni<=N-1 and 0<=nj<=N-1 and arr[ni][nj] == 0:  
                q.append((ni,nj,2))  
                cnt = 1  
            ni, nj = sti, stj +1  
            if 0 <= ni <= N - 1 and 0 <= nj <= N - 1 and arr[ni][nj] == 0:  
                q.append((ni, nj, 1))  
                if cnt == 1:  
                    for i, j in daekak:  
                        ni, nj = sti+i, stj + j  
                        if not (0 <= ni <= N - 1 and 0 <= nj <= N - 1 and arr[ni][nj] == 0):  
                            break  
                    else:  
                        q.append((ni, nj, 3))  
  
    return result  
  
N = int(input())  
arr = [[*map(int, input().split())] for _ in range(N)]  
  
# 가로의 경우  
# 가로, 오른쪽아래로만 파이프 가능  
garo = [(1,0), (1,1)]  
  
# 세로의 경우  
# 세로, 오른쪽 아래로만 파이프 가능  
sero = [(0,1),(1,1)]  
  
# 대각선의 경우  
# 세로, 가로, 오른쪽 아래 모두 가능  
daekak = [(1,1)]  
  
  
a = bfs(arr)  
  
print(a)

 

dp로 풀어주기 (pass)

• 가로의 경우 -> 현재 열 -1의 가로와 대각선의 경우의 수를 더해준다.
• 세로의 경우 -> 현재 행 -1의 세로와 대각선의 경우의 수를 더해준다.
• 대각선의 경우 -> 현재 행-1, 현재 열 -1의 가로, 세로, 대각선의 경우의 수를 모두 더해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
  
N = int(input())  
  
arr = [[0 for _ in range(N)]]  
for _ in range(N):  
    arr.append([*map(int, input().split())])  
  
# 가로 세로 대각선  
dp = [[[0,0,0] for _ in range(N)] for _ in range(N+1)]  
dp[1][1] = [1,0,0]  
  
for i in range(1, N+1):  
    for j in range(1, N):  
        if i == j == 1:  
            continue  
        if arr[i][j] == 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 arr[i-1][j] == arr[i][j-1] == 0:  
                dp[i][j][2] = sum(dp[i-1][j-1])  
print(sum(dp[N][N-1]))