https://programmers.co.kr/learn/courses/30/lessons/42898
-
flow
처음에 이 문제를 보고 카테고리가 dp라서 바로 생각의 풀이 제한되어 버렸다..
특정 칸의 최단 경로 갯수는 인접한 전칸들의 최단 경로 갯수 합이 될 것이고, 웅덩이들만 적절히 반영해주면 풀릴 문제라고 생각을 했다.
근데 막상 알고리즘을 짜려고 보니 고려해야 될 점들이 너무 많은 것 같았다.. 그리고 방향 자체도 dp면 점점 나아가야 되는데.. 특정 시점에서 모든 칸을 확인하지 않고 최단경로 갯수를 정확히 구할 수 없는 문제에 빠졌다.. 예를 들어 웅덩이 때문에 최단경로가 좌측이나 위측으로도 이동하는 경우... 길이 ㄹ 자 밖에 없다면 그것이 최단경로인데 이는 모든 칸을 확인해야 구할 수 있는 경로가 되서 dp에 적합하지 않아 고민을 많이 했다. 그러다가 질문란을 보았는데 다른 사람들은 최단경로라고 우측이나 아래측 방향만 고려하고 있었다.. 그러면 방향만 조심해서 윗칸 왼쪽칸 최단경로 갯수를 더하면 특정칸의 최단경로 갯수가 나오는 쉬운 문제가 된다.. 솔직히 억지로 dp 카테고리를 만들기 위해 짜여진 잘못 만든 문제라고 느껴지는 데다 시간도 버려서 기분이 좋진 않다. -
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level3/A15.py
