오늘은 백트래킹알고리즘 문제를 풀어보았다.
근데 백준 단계에 dfs가 있었는데.. 없어지고 바로 백트래킹이라서..
나야 해봤었는데.. 안한사람은 머리 아프겠더라.
풀 수 있나???
DFS는 모든 경로를 탐색한다. 불 필요할 것 같은 경로를 사전에 차단하거나 한는 행동이 없어서 경우의 수를 줄이지 못한다.
백트래킹은 DFS에 추가로 경로가 답이 될거 같지 않으면 돌아가는 방식이다
이를 가지치기라고 하는데 불필요한 부분을 쳐내고 하는 방식이다.
간단히 말해 특정한 조건을 만족하는 경우만 살펴보는 것이다.
백준 문젠 푼건..
주말에 정리해서 올려야겠다.
푼문제 N-Queen/스도쿠
매우 어려웠다..