문제 바로가기
문제:
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.
파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다. 파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다. 파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다. 아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.
가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.
입력:
첫째 줄에 집의 크기 N(3 ≤ N ≤ 16)이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.
출력:
첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다. 방법의 수는 항상 1,000,000보다 작거나 같다.
처음엔 dfs로 접근했다.
def dfs(x, y, z):
global cnt
# 목적지
if x == N - 1 and y == N - 1:
cnt += 1
return
# 대각선 이동
if x + 1 < N and y + 1 < N:
# 대각선 방향으로
if graph[x + 1][y + 1] == 0 and graph[x][y + 1] == 0 and graph[x + 1][y] == 0:
# 대각선 방향으로 이동.
dfs(x + 1, y + 1, 2)
# 가로 이동
if z == 0 or z == 2:
if y + 1 < N:
# 가로 방향.
if graph[x][y + 1] == 0:
# 가로 방향으로 이동.
dfs(x, y + 1, 0)
# 세로 이동
if z == 1 or z == 2:
if x + 1 < N:
# 세로 방향
if graph[x + 1][y] == 0:
# 세로 방향으로 이동.
dfs(x + 1, y, 1)
cnt = 0
N = int(sys.stdin.readline())
graph = [list(map(int,sys.stdin.readline().rstrip().split(" "))) for _ in range(N)]
dfs(0, 1, 0) # x, y: 현재 위치, z: 현재 파이프의 방향
print(cnt)
0 1 2 로 파이프의 모양을 정해준다 0은 가로 1은 세로 2는 대각선
0인 경우에는 가로와 대각선으로 갈수있고
1인 경우에는 1과 2
2인 경우에는 1과2와 3이 다 가능하다
즉 2와 0 인경우에는 가로가 가능하고 1과2인경우는 세로가 가능하고 대각선은 도착지점 기준 왼쪽 오른쪽위에가 0 이면 가능하다.
근데 이것을 dp로도 풀 수 있다고 한다.
1차원 dp도 힘든데 3차원으로한다.
내가 이해한 분 코드를 올리도록 한다.
[BOJ 17070번] 파이프 옮기기 1 (dp 풀이, python)
[BOJ 17070번] 파이프 옮기기 1 / dp 풀이, python
velog.io
다른 코드에서도 많이 쓸거같은데 제대로 숙지하고 넘어가야겠다.
댓글