배움 저장소

programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 먼저 떠오른 방법은 DFS, 정확성 테스트를 통과하였으나 효율성 테스트를 통과하지 못했다. 2차원 백터 위에서 동적할당 기법을 사용하면 된다는 생각은 했는데, 최단 거리 조건을 어떻게 넣을지 몰라 헤매다가 다른 풀이를 찾아보았다. 그런데 최단 거리 조건은 고려할 필요가 없었다. 왔던 자리를 돌아가지 않으면 최단거리 조건을 만족하기 때문이다. DP 기법을 사용할 때 ..