[BOJ] 17070 - 파이프 옮기기 1
문제 링크
문제 설명
N*N크기의 격자판 (1,1),(1,2)에 걸쳐서 파이프가 놓여있다. 파이프를 (N,N)칸까지 미뤄서 옮기려고 하는데, →, ↘, ↓의 세 방향으로만 밀 수 있다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.
아래의 사진은 파이프가 놓인 방향에 따라 밀 수 있는 경우의 수를 나타낸다.
벽을 피해서 파이프를 N*N까지 밀 수 있는 경우의 수를 구하라 .
문제 풀이
구글링하다가 안건데, 파이프 옮기기 문제는 같은 문제 다른 조건으로 두 문제가 있다. 파이프 옮기기 1은 N(3 ≤ N ≤ 16)에 1초, 파이프 옮기기 2는 N(3 ≤ N ≤ 32)에 0.5초,,,,
파이프 옮기기 1은 dfs로, 파이프 옮기기 2는 dp로 풀기를 의도하고 만든 문제인것 같은데 python을 이용해서 dfs로 1을 풀면 시간초과가 나서 둘다 dp로 풀었다 ^_ㅠ
시도 1 - dfs
dfs를 돌면서, 현재 방향에서 이동할 수 있는 모든 경우에서 재귀를 돌았다. 89%에서 시간초과 ^_ㅠ
import sys
input = sys.stdin.readline
N = int(input())
board = []
for _ in range(N):
board.append(list(map(int, input().split())))
pipe = [0,1]
pipe_dir = 0 #0:가로, 1:세로, 2:대각선
answer = 0
def in_range(x, y):
if x in range (N) and y in range(N):
return True
return False
def dfs(x, y, pipe_dir):
global answer
if x == N-1 and y == N-1:
answer += 1
return
#가로인 경우
if pipe_dir == 0 or pipe_dir == 2:
if in_range(x, y+1) and board[x][y+1] == 0:
dfs(x, y+1, 0)
if pipe_dir == 1 or pipe_dir == 2:
if in_range(x+1, y) and board[x+1][y] == 0:
dfs(x+1, y, 1)
if in_range(x+1, y+1) and board[x][y+1] == board[x+1][y] == board[x+1][y+1] == 0:
dfs(x+1, y+1, 2)
dfs(pipe[0], pipe[1], pipe_dir)
print(answer)
시도 2 - dp
dp 배열을 방향까지 포함한 3차원 배열로 만들어서 풀이한다.
상태 정의
: dir방향으로 (x,y)까지 도달할 수 있는 경우의 수
가로 :
세로 :
대각선 :
초기 상태인 dp[0][1][0]의 경우의 수를 1로 초기화해주고, 이동할 수 있는 범위 (0,2) 부터 포문을 돌면서 각각의 방향에 대해 계산해준다. 파이프가 두칸을 차지하지만 (0,1)에서 (N-1,N-1)까지 도달하면 되므로 한칸만 고려해줘도 된다.
import sys
input = sys.stdin.readline
N = int(input())
board = []
for _ in range(N):
board.append(list(map(int, input().split())))
pipe = [0,1]
pipe_dir = 0 #0:가로, 1:세로, 2:대각선
dp = [[[0]*3 for _ in range(N)] for _ in range(N)]
dp[0][0][0] = 1
dp[0][1][0] = 1
for x in range(N):
for y in range(2, N):
#대각선으로 이동
if board[x][y-1] == board[x-1][y] == board[x][y] == 0:
dp[x][y][2] = dp[x-1][y-1][0] + dp[x-1][y-1][1] + dp[x-1][y-1][2]
if board[x][y] == 0:
#가로로 이동
dp[x][y][0] = dp[x][y-1][0] + dp[x][y-1][2]
#세로로 이동
dp[x][y][1] = dp[x-1][y][1] + dp[x-1][y][2]
print(dp[N-1][N-1][0] + dp[N-1][N-1][1] + dp[N-1][N-1][2])
Author And Source
이 문제에 관하여([BOJ] 17070 - 파이프 옮기기 1), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@woo0_hooo/BOJ-17070-파이프-옮기기-1저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)