[TIL][02.25] 백트래킹, N-Queens, 위상정렬

백트래킹

해를 찾기 위해서 후보군을 나열하고, 만약 조건에 맞지 않다면 후보군에서 제외하고 돌아와 다음 후보군을 찾는 방식

백트래킹은 트리 구조를 기반으로 DFS 방식을 진행하면서 각 루트에 대해 조건에 부합했는지 체크(Promising). 만약 해당 트리에서 조건에 맞지 않는 노드를 발견한다면, 더 이상 탐색을 멈추고, 다른 노드로 가기 위해 현재 가지를 버림(Pruning).
백트래킹에서 검색할 후보들을 상태 공간 트리(State Space Tree)로 표현.

N-Queens문제

N × N 체스판에 N개의 퀸을 서로 공격하지 못하도록 배치하는 문제

8-Queens라면 8^8=16,000,000이 넘는 경우의 수를 확인해야 하는데 Pruning을 하면 약 4000~5000정도만 탐색하여 92개의 해를 얻게 됨.

위상 정렬

위상 정렬(Topological Sorting)은 방향 그래프의 정점들을 선형으로 배열하는 방법으로, 주로 의존성 문제에서 사용. 사이클이 없을 때만 가능
1. 진입 차수 계산: 각 정점의 진입 차수(해당 정점으로 들어오는 간선의 수)를 계산합니다.
2. 큐에 추가: 진입 차수가 0인 정점을 큐에 추가합니다.
3. 정점 처리: 큐에서 정점을 하나씩 꺼내어 결과 리스트에 추가하고, 그 정점과 연결된 모든 정점의 진입 차수를 감소시킵니다. 만약 진입 차수가 0이 되는 정점이 있다면 큐에 추가합니다.
4. 결과 확인: 모든 정점을 처리했는지 확인합니다. 처리된 정점의 수가 원래 정점의 수와 같다면 위상 정렬이 성공한 것

그룹과제

백준2252

[JAVA]백준 - 2252번 줄 세우기(골드3)

SWEA1251

[JAVA]SWEA - 2001 파리 퇴치 (D2)