[Java/C++] 프로그래머스 Level 3 - 보행자 천국

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/1832 2017년도 그러니까 6년 전쯤에 카카오 코딩 테스트에서 나온 문제 현재의 카카오 코딩테스트 출제 스타일이 다른 느낌 요즘은 DP 잘 안 나온다던데.. 문제 핵심 및 풀이 DFS나 BFS로 풀면 시간초과 아직까지 이해가 가지 않는 부분이다.

DFS의 최적의 시간복잡도는 O(V+E)이다. 그래서 문제 조건상 최대 500 * 500 * 2이기 때문에 DFS를 돌려도 시간초과가 뜰 리가 없다고 생각했다.

그런데 해당 방법은 시간초과가 뜨고 다른 방법을 사용해야 했다. 내 상식으로는 이해할 수가 없는데..

아시는 분..? DP로 문제 접근 두 번째로 생각해 볼 수 있는 가능성은 DP였다. .....