3109

[백준 3109] 빵집 C++

3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 이 문제는 그리디 알고리즘을 적용한 DFS문제이다 그리디를 어떻게 적용하는가?? 항상 오른쪽 위 부터 탐색을 해야한다(0번째 Row부터 탐색할 경우만 해당. R-1번째 부터 탐색하면 오른쪽 아래부터 탐색) 탐색을 한 부분은 다시 탐색하지 않는다! (DP개념도 같이 적용) 문제를 이해했다면 항상 오른쪽 위 부터 탐색해 간다는건 쉽게 이해할 수 있다 나도 처음엔 이것만 생각해서 백트래킹 방식을 적용해 37 번 라인에 방문했던 곳을 초기화 해주는 코드(Map[r][c] = 0;)가 ..