Algorithm/BackTracking2 [Algorithm] BackTracking / Java BackTracking = DFS + prunning ✔ 백트래킹이란? 백트래킹은 한마디로 가지치기(prunning)를 가미한 너비우선탐색(DFS)입니다. 다시 말해서, DFS로 해를 찾아가는 과정에서 수시로 현재 경로의 유망성을 판단하여 유망하지 않음이 판단되면 더이상 나아가지 않고 이전 노드로 돌아가 다른 경로를 탐색하는 방식입니다. 이어서 백트래킹과 완전탐색을 비교함으로써 백트래킹의 특성을 알아보겠습니다. ✔ 백트래킹과 완전탐색(DFS)의 차이 완전탐색과 구분되는 백트래킹의 핵심적인 특성은 '가지치기'에 있습니다. 완전탐색이 모든 경로를 탐색하는 데 반해 백트래킹은 불필요한 경로를 조기에 차단함으로써 탐색 소요를 줄입니다. 따라서 백트래킹의 효율성은 가지치기의 조건에 달려있다고 볼 수 있습니다. 다.. 2023. 8. 16. [백준] 9663. N-Queen / Java https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 이 문제는 크기가 N * N인 체스판 위에 퀸 N 개를 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제이다. 기본적으로 BruteForce 유형이나 isPromising()과 같은 메서드를 활용하여 가망이 없는 경로를 가지치기 하며 진행하는 BackTracking 기법이 가미되어 있다. 우선 눈여겨 볼 점은 이 차원으로 이루어진 체스판을 일 차원 배열(board[])로 바꾸어 생각한다는 것이다. 배.. 2023. 6. 14. 이전 1 다음
