Traversal

백트래킹 (Backtracking)

백트래킹 (Backtracking) ** 아래 포스팅 내용 관련하여, 더 나은 방법이나 아이디어가 있으신 경우에는 댓글에 의견을 공유해주시면 감사하겠습니다. ** Source code는 C 언어로 작성되었습니다. 백트래킹(Backtracking)의 특징 백트래킹은 말 그대로 '역추적'을 의미합니다. 문제 해결을 위한 모든 경우의 수를 따져보기 위해서 (완전 검색 (Exhaustive search), 실제로 모든 케이스를 다 직접 확인한다는 의미는 아니지만) 일반적으로 활용되는 기법 중 하나입니다. 백트래킹은 우선 어떤 하나의 가능한 케이스를 확인하고, 가능하지 않다면 다시 Back하고, 다시 다른 가능성있는 케이스를 확인하면서 Solution이 도출될 때까지 이런 과정이 계속적으로 반복되도록 구현하게 됩..

너비 우선 탐색 (BFS, Breadth First Search)

너비 우선 탐색 (BFS, Breadth First Search) ** 아래 포스팅 내용 관련하여, 더 나은 방법이나 아이디어가 있으신 경우에는 댓글에 의견을 공유해주시면 감사하겠습니다. ** Source code는 C 언어로 작성되었습니다. 그래프 순회 (Traversal) 알고리즘 : 너비 우선 탐색 (BFS) 그래프 순회 알고리즘이란, 그래프 상에 표시된 모든 지점 (node) 들을 방문해야 하는 경우 사용되는 알고리즘을 의미합니다. 요구 사항이나 그래프 형태, 각 노드의 가중치나 특성에 따라서 순회 알고리즘의 세부 구현 방식은 달라질 수 있습니다. 그러나 그래프 순회 알고리즘에서 공통적으로 가장 중요한 것은 한 번 방문한 node를 다시 방문하지 않도록 표시하는 것입니다. 이 부분이 잘못 처리될 ..