[BOJ] 1520 내리막 길

https://www.acmicpc.net/problem/1520

틀렸던 문제를 다시 도전했지만 또 틀린 문제다.

시도 1 - 실패

처음에는 DP인줄 생각 안 하고 BFS로 모든 경로를 다 찾아보려고 했다. 도착지에 갈 때마다 숫자를 세서 답을 구했다. 그리고 시간 초과가 났다.

from collections import deque

n, m = map(int, input().split())

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

visited = [[True] * m for _ in range(n)]

que = deque()
idx = 0

que.append((0, 0))

dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]

count = 0

while que:
  y, x = que.popleft()
  
  if y == n-1 and x == m-1:
    count += 1
    continue
  
  for d in range(4):
    ny = y + dy[d]
    nx = x + dx[d]
    
    if 0 <= ny < n and 0 <= nx < m and map[y][x] > map[ny][nx]:
      que.append((ny, nx))
      
print(count)

시도 2 - 실패

BFS는 안 되니 DFS로 찾아보려고 했다. DFS로 마지막 점에 도달할 때마다 숫자를 세서 답을 구했다. 이거도 시간초과가 났다.

n, m = map(int, input().split())

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

visited = [[True] * m for _ in range(n)]
count = 0

dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]

visited = [[True] * m for _ in range(n)]
visited[0][0] = False

def dfs(start, visited):
  global count
  if start[0] == n-1 and start[1] == m-1:
    count += 1
    return
  
  y, x = start
  
  for d in range(4):
    ny = y + dy[d]
    nx = x + dx[d]
    
    if 0 <= ny < n and 0 <= nx < m and map[y][x] > map[ny][nx] and visited[ny][nx]:
      visited[ny][nx] = False
      dfs((ny, nx), visited)
      visited[ny][nx] = True
      
dfs((0, 0), visited)

print(count)

시도 3 - 실패

도저히 안 돼서 예전 코드를 찾아봤다. 예전 코드에서는

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

dy = [0, 1, -1, 0]
dx = [1, 0, 0, -1]

ans = 0
# 특정 점까지 도달할 수 있는 경우의 수 기록용
memo = [[-1] * m for _ in range(n)]
memo[n-1][m-1] = 1

def dfs(y, x):
  if memo[y][x] != -1:
    return memo[y][x]

  memo[y][x] += 1
  for d in range(4):
    ny = y + dy[d]
    nx = x + dx[d]
    if 0 <= ny < n and 0 <= nx < m and maps[ny][nx] < maps[y][x]:
      memo[y][x] += dfs(ny, nx)
  return memo[y][x]

print(dfs(0, 0))

위와 같이 memo를 활용해서 특정 점까지 도달할 수 있는 경우를 기록했고 그 기록을 기반으로 다음 칸까지 도달할 수 있는 경우를 구했다. 그래서 비슷하게 하지만 거슬리는 부분은 없게 코드를 다시 짰고 다음과 같다.

n, m = map(int, input().split())

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

dy = [0, 0, 1, -1]
dx = [1, -1, 0, 0]

visited = [[0] * m for _ in range(n)]

visited[n-1][m-1] = 1

def dfs(start):
  y, x = start
  
  if visited[y][x] == 0:
    return visited[y][x]
  
  for d in range(4):
    ny = y + dy[d]
    nx = x + dx[d]
    
    if 0 <= ny < n and 0 <= nx < m and map[y][x] > map[ny][nx]:
      visited[y][x] += dfs((ny, nx))
  
  return visited[y][x]

print(dfs((0, 0)))

그리고 실패했다. 예전에 저렇게 코드 짤 때도 의문이었는데 -1로 memo를 초기화하면 통과하지만 0으로 초기화하면 통과하지 못하는 문제가 있었다.
고민해보고 지피티 선생님께 여쭤본 결과 0으로 초기화하게되면 0이 의미하는게 모호해진다고 했다.

1. 방문하지 않아서 0
2. 방문했으나 그냥 값이 0

이렇게 두 가지 의미를 갖게돼서 계속 연산이 일어나는 거라고 했다. 그래서 최초에 -1로 초기화 함으로써 방문기록을 구분시키게 되면 그 뒤로는 정상적으로 작동하는 것이라고 한다.