16936 나3곱2

https://www.acmicpc.net/problem/16936

16936번: 나3곱2

 

골드5에 적절한 난이도이지 않을까 싶다

문제도 깔끔하다

 

부르트포스는 절대 안되고, 최적해를 구해야 하니 그리디도 안된다

그렇다고 부분문제를 이용해서 DP테이블을 짜는 그런 것도 아니다

 

그러다가 dfs bfs 인가? 싶어서 생각해봤더니 가능해보여서 그래프 순회 느낌으로 풀었다

 

처음엔 bfs로 풀려 했는데, 결국엔 경로를 출력하는게 최종 목표이니, bfs로는 그게 좀 까다롭고 힘들어서

 

dfs로 바꿔서 풀었다

 

결론은 흔한 dfs에 조건 몇개 추가해주면 된다

백트래킹이 사용됐는데, 솔직히 백트래킹이랑 dfs 엄밀히 구분하기가 넘 힘듬

 

https://github.com/KimximyaFan/Random-Defense/blob/main/C0022.java