https://www.acmicpc.net/problem/15649
Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net대부분의 초보들이 N과M (1) 으로 백트래킹을 입문하는 것에 대해서는 이견의 여지가 없을 것이다
시발 이거 어케 푸노 하면서 블로그 찾아보면
코드 띡 하고 내놓고 이게 백트래킹이에요 ^^
하고 배울텐데
상태, 즉, 여기 고수 분들이 쓰는 용어로는 state
아무튼 대부분의 블로그에서, 상태에 대한 개념과 설명이 부재하다보니
dfs와 백트래킹이 뭔 차이가 있는지 이해하지 못하는 것이다
사실 근데 state를 설명하라고 하면 또 너무 추상적이고 막연하긴 하다
아무튼
백트래킹이란, 이전 state로 되돌아가는 방식이 필요한 순회 방법이고
이걸 구현하기 제일 쉬운 방법이 dfs임을 깨닫는데 까지, 즉,
dfs와 백트래킹이 어떤 개념의 차이가 있는지를 깨닫는데 나는 꽤 오랜시간이 걸린 범부였을 뿐이다
난 저 문제 처음봄 그냥 nCr 조합구하는 과정과 N퀸 문제로 백트래킹개념 접했는데 사실 그냥 다필요없고 "가지치기" 한단어로 설명되는거아님? 가지치기를 잘하고 못하고는 개인 지능차이고
맞말인데 왜케 비추가 많음
맞는말인데 왜비추... - dc App
권위 없어보이는 사람이 뭔가 설명하려들면 거부감 들어서 비추하는건가 뭐지
엄청난 깨달음을 얻은 현자같으시네요 ㅋㅋ
그저 관점중 하나일 뿐임
너의 설명을 통해 백트래킹을 이해할 수 있다는건 참임, 하지만 백트래킹을 이해하기 위해 너의 설명이 필요하진 않음. 너는 트리를 탐색하는데 사용할 수 있는 도구인 DFS를 백트래킹의 도구로써 이해하고있고, 여기서 상태라는 개념을 통해 백트래킹을 동적인 개념으로 이해했지 정 반대로 정적인 해석도 가능함
아무 예시나 들어볼게 어떤 노드 n에 담긴 정보가 2-튜플 (부모 노드에 담긴 정보, n과 부모 노드 사이 간선의 정보)과 일대일 대응될 때, 이런 노드만으로 구성된 트리를 "적절한 트리"라고 부르자. 백트래킹을 "적절한 트리"에서 조건을 만족하는 임의의 리프 노드를 찾는 알고리즘이라고 정의하면, 백트래킹은 그저 트리 탐색의 특수한 케이스가 될 뿐임. 이 설명에 상태같은건 필요 없음
마지막으로 주장을 확실하게 하자면 네가 백트래킹을 해석한 방법이 틀렸다는게 아니라, 백트래킹의 설명에서 상태의 개념이 절대적인 지위를 가지지 않는다고 부정하는것임. 상태를 설명할 필요가 없기 때문에 상태의 개념 없이 백트래킹이 지금껏 설명됐고, 상태라는 개념을 이해하지 않아도 됨.
물론 상태를 통해 백트래킹을 설명하는 사람들 역시 존재한다
랜디돌리면서, '어 이거 백트래킹인데?' 하고 자유자재로 적용, 응용해서 문제해결을 하려면 아무튼 상태 이해는 꼭 필요함
초보자들이 쓰는 재귀는 나는 모르겠고 시발 일단 타고 들어가서 찾아봐 그리고 초보자 벗어난 애들이 상태를 기록하는 것에 그치는거지 그 상태를 다룬 다는 건 고수들만 가능함