[dfs] 백준 빵집 문제에 대한 고찰, python

🤔 왜 풀지 못했을까?

이번 문제는 다른 문제들과 다르게 dfs와 함께 그리디 알고리즘이 결합된 형태의 문제였다. 처음 보는 유형에 많이 당황도 했지만 설마 이 방법으로? 라는 생각에 알고리즘의 정당성을 증명하지 못했다.

여기서 그리디 적으로 생각한다는 것은 8방향중에 어차피 갈 수 있는 방향은 오른쪽으로 움직이는 것 밖에 없기 때문에 [-1, 1][0, 1][1, 1] 이 셋을 dfs알고리즘을 통해 접근하지 못한다면 어차피 갈 수 없기 때문에 3개만 확인함으로써 시간안에 들어 올 수 있게 된다.

또한 그뿐만이 아니라 dfs를 재귀적인 방법을 통해 check해야할 곳만 가는 것도 떠올리지 못했다. 매번 스택으로 구현해서 도달하지 않은 부분들 까지도 다 방문처리 되는 것을 막기위해 재귀적으로 구현하는 것이 더 편했던 방법인 것 같다.

내 답안 링크이다.
https://github.com/Deserve82/KK_Algorithm_Study/blob/master/Kangho/BOJ_3109.py

코테 풀기전에 이런 좋은 문제를 풀 수 있어서 다행이었다.