leah

my dev_log

0%

BOJ 1520

Posted on In ,

Input

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다.

이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

1
2
3
4
5
6
from collections import deque
import sys
input = sys.stdin.readline

m, n = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(m)]

DP + DFS

처음에 시도했던 방법은 BFS + 스택 을 이용했다. 답은 나오는데 시간 초과가 떠서 실패했음. 생각해보니 스택을 쓰면 끝까지 가서 아닌 경우를 계속 체크하는 바람에 시간이 초과될 수밖에 없겠더라. 코드는 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def bfs(cnt):
  s = deque()
  s.append((0,0))

  while s:
    dx, dy = s.pop()

    for d in dir:
      x = dx + d[0]
      y = dy + d[1]

      if x == m-1 and y == n-1:
        cnt += 1
        break

      if 0 <= x < m and 0 <= y < n:
        if board[x][y] < board[dx][dy]:
          s.append((x, y))

  return cnt

print(bfs(0))

그리고 가만 보면 DFS만으로 해결할 수 있겠다 싶은 문제이지만, 시작점과 도착점이 고정되어 있는 상태에서 경우의 수를 체크하는 문제이기 때문에 DP 로 접근해야 한다. 근데 계속 트리 가지를 쳐가며 들어가는 문제이기 때문에 DFS 까지 결합됨.

조건을 살펴보면,

  • 상하좌우로만 이동 가능

  • 현재 지점보다 높이가 낮아야

일단 DFS이기 때문에 재귀 호출 한계를 설정해주고, DP로 각 DFS 시점의 방문지점을 체크하는 배열인 동시에 시작점에 도달했을 시 count++를 해주는 배열을 생성한다. 이 때, (0,0)에 도달했을 때만 count++를 해주어야 하므로 dp를 -1로 초기화하고, 방문하면 0으로 설정하여 dfs를 해나감에 있어서 count에 영향이 없도록 한다.

1
2
3
4
5
6
7
8
sys.setrecursionlimit(100000)

# dp: 각 경우의 visited + count 동시에 역할
# (0,0)에 도달했을 때만 cnt+1 되어야 하므로 -1으로 초기화하고,
# 방문 체크용으로는 0으로 해야 +에 지장이 없음.
dp = [[-1]*n for _ in range(m)]

dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]

그리고 DFS를 정의해준다.

  • (0, 0)에 도달하면 count++: return 1

    1
    2
    3
    4
    5
    # 도착점 fix된 경우: parameter로 도착점 설정
    def dfs(x, y):
      # 시작점 fix된 경우: return 경우 설정
      if x == 0 and y == 0:
        return 1

  • 처음 방문한 경우 dp를 0으로 세팅 (답이 존재하든 아니든 일단 방문했으므로 0으로 세팅해야 함) 하고, 상하좌우 이동 시 범위 내에 해당하면서 조건을 만족한다면 지금의 경로를 도착점 dp에 저장한다.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    # 방문 전
    if dp[x][y] == -1:
      # 답이 있건 없건 방문 체크해야 함
      dp[x][y] = 0
      
      for d in dir:
        nx = x + d[0]
        ny = y + d[1]
      
        if 0 <= nx < m and 0 <= ny < n:
          # 목표 지점(현재 지점)보다 방문할 곳이 큰 경우 = 조건
          if s[x][y] < s[nx][ny]:
            ### 전체 경로 (경우의 수) 체크 가능
            dp[x][y] += dfs(nx, ny)

Output

첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.

  • 결국 모든 경로의 수가 저장된 것은 dp[x][y] 이므로 이를 출력한다.
1
return dp[x][y]
1
print(dfs(m-1, n-1))