| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 512 MB | 32064 | 15018 | 10307 | 45.726% |
문제
유현이가 새 집으로 이사했다. 새 집의 크기는 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보다 작거나 같다.
답안
import sys
from enum import IntEnum
class State(IntEnum):
HORIZONTAL = 0
VERTICAL = 1
DIAGONAL = 2
n = int(sys.stdin.readline())
obstacles = [list(map(lambda x: bool(int(x)), sys.stdin.readline().split())) for _ in range(n)]
memo = [[[0, 0, 0] for _ in range(n)] for _ in range(n)]
memo[0][1][State.HORIZONTAL] = 1
answer = 0
for i in range(n):
for j in range(1, n):
if obstacles[i][j]:
continue
memo[i][j][State.HORIZONTAL] += memo[i][j-1][State.HORIZONTAL] + memo[i][j-1][State.DIAGONAL]
if i == 0:
continue
memo[i][j][State.VERTICAL] += memo[i-1][j][State.VERTICAL] + memo[i-1][j][State.DIAGONAL]
if not obstacles[i-1][j] and not obstacles[i][j-1]:
memo[i][j][State.DIAGONAL] += sum(memo[i-1][j-1])
print(sum(memo[n-1][n-1]))풀이
이 문제를 보았을 때 DP로 문제를 해결하면 좋을 것 같지만 마땅한 세부적인 해결 방법이 생각나지 않을 수 있을 것이다.
위치 x, y값을 나타내는 값들을 이용해 이전에 메모이제이션된 값을 활용해 계산하면 되지 않겠는가? 라는 지점까지 도달했지만 더이상 진척이 없는 경우 차원을 높이는 것이 해결 방안이 될 것이다.
위 문제에서 파이프는 x, y 값뿐만 아니라 파이프의 상태(가로, 세로, 대각선)에 따라서 앞으로 가질 수 있는 위치 값과 파이프의 상태 값이 달라질 수 있으므로, 메모이제이션 배열의 차원을 높여 x, y, 그리고 파이프의 상태까지 저장하게 한다.
그렇게 된다면 다음과 같이 정리할 수 있다.
- 위 그림 중 노란색으로 칠해진 경우는 이동 후 파이프의 상태가 가로인 경우이다.
파이프의 상태가 가로가 되려면, 위 두 경우에 속해야만 한다. (파이프를 움직이지 않은 초기의 경우도 여기에 포함됨)
따라서 노란색으로 칠해진 칸에 가로 상태로 도달하기 위한 경우의 수를 구하기 위해서는 가로 상태, 혹은 대각선 상태에서 가로로 민 경우를 각각 더하면 된다. - 위 그림 중 초록색으로 칠해진 경우는 이동 후 파이프의 상태가 세로인 경우이다.
파이프의 상태가 세로가 되려면, 위 두 경우에 속해야만 한다.
따라서 초록색으로 칠해진 칸에 세로 상태로 도달하기 위한 경우의 수를 구하기 위해서는 세로 상태, 혹은 대각선 상태에서 세로로 민 경우를 각각 더하면 된다. - 위 그림 중 파란색으로 칠해진 경우는 이동 후 파이프의 상태가 대각선인 경우이다.
파이프의 상태가 대각선이 되려면, 위 세 경우에 속해야만 한다.
따라서 파란색으로 칠해진 칸 중 파이프의 오른쪽 아래 끝이 위치한 칸에 대각선 상태로 도달하기 위한 경우의 수를 구하기 위해서는 가로 상태에서 가로로 민 뒤 회전시키거나, 세로 상태에서 세로로 민 뒤 회전시키거나, 대각선 상태에서 대각선으로 민 경우의 수를 각각 더하면 된다. - 단, 위 세 경우 모두 색이 칠해진 칸에 장애물이 없어야 하며, 파이프가 격자 밖으로 나가면 안된다.
위에서 설명한 것들을 구현한 것이 아래 코드이다. 더 빠른 이해를 위해 장애물과 격자 바깥 조건을 구현한 부분은 생략하였다.
memo[i][j][State.HORIZONTAL] += memo[i][j-1][State.HORIZONTAL] + memo[i][j-1][State.DIAGONAL]
memo[i][j][State.VERTICAL] += memo[i-1][j][State.VERTICAL] + memo[i-1][j][State.DIAGONAL]
memo[i][j][State.DIAGONAL] += sum(memo[i-1][j-1])네 번째 조건까지 구현하면 다음과 같다.
for i in range(n):
for j in range(1, n):
if obstacles[i][j]:
continue
memo[i][j][State.HORIZONTAL] += memo[i][j-1][State.HORIZONTAL] + memo[i][j-1][State.DIAGONAL]
if i == 0:
continue
memo[i][j][State.VERTICAL] += memo[i-1][j][State.VERTICAL] + memo[i-1][j][State.DIAGONAL]
if not obstacles[i-1][j] and not obstacles[i][j-1]:
memo[i][j][State.DIAGONAL] += sum(memo[i-1][j-1])입력을 받아준 뒤, 위에서 설명한 로직을 적용시킨 후 가장 오른쪽 하단 칸의 모든 파이프 상태에 대한 경우의 수 값의 합을 출력해주면 된다.
print(sum(memo[n-1][n-1]))from enum import IntEnum
class State(IntEnum):
HORIZONTAL = 0
VERTICAL = 1
DIAGONAL = 2그리고 특별히 이 문제를 풀기 위해 IntEnum을 사용했는데, Enum에 비해 IntEnum이 제공하는 것은 IntEnum은 integer 즉 정수로 매핑될 수 있다는 것이다. 따라서
memo[i][j][State.HORIZONTAL]와 같은 상황에서 일반적인 Enum을 사용하게 되면 인덱스 자리에 정수가 들어가 있지 않아 예외를 발생시키겠지만, IntEnum을 사용함으로써 그러한 문제를 해결하였다.
