[백준 2507번] 공주 구하기 (Python3)

import sys
input = sys.stdin.readline

def DFS(x1,x2):
  DP[x1][x2] = 0
  M = max(x1,x2)+1
  for next in range(M,N-1):
    if not graph1[x1][next]:
      break
    if DP[next][x2]==-1:
      DFS(next,x2)
    DP[x1][x2] += DP[next][x2]
  for next in range(M,N-1):
    if not graph2[x2][next]:
      continue
    if DP[x1][next]==-1:
      DFS(x1,next)
    DP[x1][x2] += DP[x1][next]
  DP[x1][x2] += int(graph1[x1][-1]==graph2[x2][-1]==1)
  DP[x1][x2] %= 1000

N = int(input())

data = [[*map(int,input().split())] for i in range(N)]
graph1,graph2 = [[[0]*N for i in range(N)] for i in range(2)]

for i in range(N):
  x,d,p = data[i]
  for j in range(i+1,N):
    if data[j][0]>x+d:
      break
    graph1[i][j] = 1
  if p:
    for j in range(i-1,-1,-1):
      if data[j][0]<x-d:
        break
      graph2[j][i] = 1

DP = [[-1]*N for i in range(N)]
DFS(0,0)
print(DP[0][0])

DFS+DP로 해결하였다.

 

처음에는 풀이가 전혀 생각나지 않는 문제였다. 그러다가 NP-hard [백준 9520번] NP-hard (Python3) (tistory.com) 문제를 풀었는데, NP-hard 문제가 경찰차 [백준 2618번] 경찰차 (Python3) (tistory.com) 문제와 사실상 같은 문제라는 사실을 알게되었다.

즉, "1번 지점에서 N번 지점까지 갔다가 돌아오기" 를 "1번 지점에서 N번 지점까지 두 번 이동하기" 로 치환할 수 있다는 것이다. 이 사실을 알고 나자 '어 그럼 이걸 이용하면 저번에 봤던 공주 구하기 문제도 비슷하게 풀 수 있겠는데?' 하는 생각이 들었고, 실제로 해결할 수 있었다.

 

풀이를 설명하면,

1. graph1, graph2를 만든다. graph1은 현재노드에서 오른쪽으로 뛰었을 때 이동가능한 노드를 1로 표시한 인접행렬, graph2는 각 노드에서 왼쪽으로 뛰었을 때, 현재 노드에 '도착'가능한 경우 1로 표시하는 인접행렬이다. (출발, 도착 주의)

2. DP[x1][x2]는 x1를 밟으면서 N에 도착하고 x2를 밟으면서 돌아오는 경우의 수이다. 다른말로 하면 두 사람이 0에서 출발해서 한명은 x1, 한명은 x2에 있을 때 둘 다 N에 도착하는 경우의 수이다.

3. x1은 graph1을 x2는 graph2을 통해 이동한다. 이때 이동할 때에는 max(x1,x2)보다 큰 지점으로만 이동할 수 있다. (중복방지)

4. x1과 x2 모두 N으로 갈 수 있으면 +1을 한다.

5. DFS를 하여 DP[0][0]를 출력한다.

 

경찰차 문제와 풀이가 거의 유사하다. "갔다가 돌아오기 = 두번 이동하기" 라는 특성을 알면 쉽게 해결할 수 있는 문제였다.

 

 

오늘의 교훈) 왕복이동은 두번 이동하는것으로 치환할 수 있다.