문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42898
이 문제는 카테고리가 다이나믹 프로그래밍으로 분류된 만큼 동적 계획법을 이용한 방법으로 풀이를 하지 않으면 효율성 검사에서 시간 초과가 나오도록 설계되어 있다.
따라서 동적 계획법의 memoization 또는 tabulation을 사용하여야 하는데 여기서 이 두 방법에 대해 간단하게 설명하고 지나가도록 하겠다.
Memoization
- 마치 지나간 길(재귀)을 메모하듯이 탐색한다고 해서 붙혀진 이름 (뇌피셜)
- Top-Down 방식으로 일단 Goal(Top)를 먼저 호출하는 방식
- 현재 노드의 값을 알 수 없을 때(필요할 때), Down 노드를 호출하면서 작은 값들을 구해나가는 방식(Lazy Evaluation)
- 재귀 형식을 띄며 사실상 dfs와 같지만 Memo를 하고 안하고의 차이가 존재
- memo를 할 배열, 리스트와 같은 자료구조를 필요로 하며 상황에 따라 크기가 n에서 constant인 경우로 줄일 수도 있음
Tabulation
- 표에 전부 적어 넣는다고 해서 붙혀진 이름 (뇌피셜)
- Bottom-Up 방식으로 1(Bottom)부터 시작해서 Goal(Up)을 향해 연산을 지속
- 나중에 필요한지 아닌지는 모르지만 일단 전부 구해놓는 방식(Eager Evaluation)
- for문을 이용해 전부 순회하듯이 연산할 수 있으며 가독성이 memoization에 비해 떨어질 수 있음, 하지만 호출관계가 복잡하지 않아 구현하는 입장에서 편하다고 생각됨
- tabulation으로 사용할 배열, 리스트가 필요하며 상황에 따라 크기를 constant하게 줄일 수도 있음
문제는 등굣길이라는 가상의 map이 존재하고 이 map에 폭우로 인해 웅덩이(지나갈 수 없는 길)이 존재한다는 스토리이다. 웅덩이를 피해 집(1,1)에서 학교(m,n)까지 가는 최단 거리를 구하는 문제이다. 집이 좌상단에 있고 학교는 우하단에 있으므로 맨해튼 거리와 비슷하게 생각하면 될 것 같다. 이때 좌표를 벗어나지 않도록 주의해야 하며, 계산에 중복이나 정확한 호출 관계를 생각하고 풀이하면 좋을 것 같다.
이번에 구현한 방식은 Memoization이다. 요즘 재귀를 사용한 기억이 거의 없어서 한번 테스트해볼 겸 해서 구현해 보았다. 예전에는 괜히 재귀를 사용하면 어려워서 꺼려했었는데 지금보니까 가독성이 선녀다...
위에 Memoization 설명에서 볼 수 있듯이 거의 dfs와 진행 방식이 동일하며 구한 값을 map이라는 2차원 리스트에 memo하는 부분만 다르다고 볼 수 있다.
solution에서는 일단 dfs(m-1, n-1, map)으로 학교에 도착하는 최단거리를 요청하고 시작하면 된다. map에서 길은 0이고 집은 1, 웅덩이는 -1로 초기화했다.
그러면 이제 우리는 dfs()를 구현하면서 왼쪽과 위쪽의 값을 더해주기만 하면 된다.
그 외의 방향에서 오면 최단거리가 아니다!
이때 좌표를 벗어나거나 웅덩이가 해당 방향에 있으면 0으로 return 해준다.
끝!
def solution(m, n, puddles):
map = [[0 for _ in range(m)] for _ in range(n)]
for x, y in puddles:
map[y-1][x-1] = -1
map[0][0] = 1
return dfs(m-1, n-1, map)
def dfs(x, y, map):
if x < 0 or y < 0 or map[y][x] == -1:
return 0
if map[y][x] == 0:
map[y][x] = dfs(x-1, y, map) + dfs(x, y-1, map)
return map[y][x] % 1000000007