본문 바로가기

Greedy1

[백준] 3109. 빵집 풀이 DFS를 통해 탐색을 진행할 때 최대값을 찾는 경우는 대부분 모든 경우의 수를 확인해야 하기 때문에 유망하지 않은 경우 가지치기하는 백트래킹 방법을 사용할 수 없다. 하지만 이 문제는 시작 점은 가장 위에서부터 연결할 수 있는 경우에는 연결하는 경우가 최선의 방법이 되는 그리디한 접근 방식을 사용하였고 이를 통해 유망하지 않은 경우 탐색을 종료하는 경우 되돌아가는 백트래킹 방식을 사용하였다. 첫번쨰 열의 1번쨰 행부터 탐색을 진행하고, 만약 C번째 행에 도착했다면 이번 시작 위치에서의 탐색을 종료한다. 다음 위치도 동일하게 진행하는데 만약 실패한다고 하더라도 방문한 위치에 대한 체크를 되돌리지 않는다. 왜냐하면 해당 위치에서 파이프를 완성하지 못했다고 하더라도 뒤 선택지에서 해당 방향은 동일하게 실.. 2021. 2. 19.

이전 1 다음

티스토리툴바