백준[BOJ] 1520번 : 내리막길

1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 처음 문제의 이미지를 보자마자 깊이우선탐색/넓이우선탐색 문제일것이라는 생각이 들었다. 경로의 개수를 찾아야하는 이 문제에서는 DFS가 적합하다는 직감이 느껴졌다. 이 문제에서는 여러 종류의 경로가 서로 중첩되는 경우를 반드시 고려해야한다. 만약 BFS로 탐색을 진행하게 되면 가능한 모든 경로를, 같은 깊이로, 탐색을 진행한다. 이 때에는 (다른 깊이, 같은 지점)에서 만났을 경우를 처리하는 게 복잡하다고 생각된다. 이 글 쓰고 나서 시도해봐야겠다. DFS로 가능한 하..

원문링크 : 백준[BOJ] 1520번 : 내리막길