안녕하세요, 오늘은 백트래킹의 가장 대표 유형 문제인 N-Queen 문제를 풀이해보겠습니다. https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 핵심 로직 - 백트래킹 (재귀 활용) 풀이 방식 1. 가장 윗 열부터 시작하여 퀸을 놓을 수 있는 지, 없는 지 여부 확인 > 조사 범위를 윗..
백트래킹
안녕하세요 오늘은 백트래킹에 대한 포스팅을 작성해보겠습니다. 목차 1. 백트래킹 기법 2. DFS와의 차이점 3. 대표적 문제예시 4. N-Queen 코드 한 줄 요약 백트래킹은 모든 후보 검사가 아니다, 즉 완전탐색이 아니다. 1. 백트래킹 기법 어떤 노드의 유망성을 점검한 후 에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 간다. 가지치기(pruning): 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않는다. 2. 백트래킹과 DFS와의 차이 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 그 경로를 따라가지 않음으로써, 시도 횟수를 줄인다. 깊이 우선 탐색이 모든 경로를 추적하는데 비해 백트래킹은 불필요한 경로를 조기에 차단할 수 있다. N! 가지의 경우..
