https://www.acmicpc.net/problem/17069
17069번: 파이프 옮기기 2
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의
www.acmicpc.net
dp 문제임을 깨달으면 접근할만 한데
어려운 이유는 dp임을 깨닫기가 쉽지 않다.
첫 시도를 bfs로 했었고 마지막 예제에서 시간 초과가 발생했다.
풀이 방법은,
dp는 3차원 리스트로 만든다. n*n*3이다.
마지막이 3인 이유는 각 horizontal, vertical, diagonal 방향의 정보를 담고 있어야 하기 때문.
처음엔 모든 성분을 0으로 초기화해준다.
그 후 순차적으로 탐색하면서,
1. 내 아래, 옆, 대각의 graph 값이 모두 0이다 -> 즉 모두 뚫려 있다 -> 대각 이동 가능!
-> 그럼 현재 나의 방향이 뭐든 간에 대각으로 갈 수 있기 때문에 dp[i + 1][j + 1][2] += sum(dp[i][j])
dp[i + 1][j + 1][2]인 이유? 대각으로 가면 나의 방향이 무조건 대각이 되니깐.
2. 내 옆의 graph 값이 0 -> 옆이 뚫려 있다 -> 수평 이동 가능!
-> 나의 현재 방향이 대각선 또는 수평일때만 수평으로 갈 수 있다.
따라서 dp[i][j + 1][0] += dp[i][j][0] + dp[i][j][2]
dp[i][j + 1][0]인 이유? 옆으로 가면 나의 방향이 무조건 수평이 되니깐.
3. 내 아래의 graph 값이 0 -> 아래가 뚫려 있다 -> 수직 이동 가능!
-> 나의 현재 방향이 대각선 또는 수직일때만 수직으로 갈 수 있다.
따라서 dp[i + 1][j][1] += dp[i][j][1] + dp[i][j][2]
dp[i + 1][j][1]인 이유? 아래로 가면 나의 방향이 무조건 수직이 되니깐.
n = int(input())
graph = []
for _ in range(n):
graph.append(list(map(int, input().split())))
def check(x, y):
if graph[x+1][y] == 0 and graph[x][y+1] == 0 and graph[x+1][y+1] == 0:
return True
return False
## [h, v, d] -> direction
dp = [[[0 for _ in range(3)] for _ in range(n)] for _ in range(n)]
dp[0][1][0] = 1
for i in range(n):
for j in range(1, n):
if i+1 < n and j+1 < n and check(i, j):
dp[i + 1][j + 1][2] += sum(dp[i][j])
if i < n and j+1 < n and graph[i][j+1] == 0:
dp[i][j + 1][0] += dp[i][j][0] + dp[i][j][2]
if i+1 < n and j < n and graph[i+1][j] == 0:
dp[i + 1][j][1] += dp[i][j][1] + dp[i][j][2]
print(sum(dp[-1][-1]))
댓글