💡 URECA/🗒️ 스터디 노트
[URECA] Day22 | 알고리즘 | 그래프 응용(백트래킹, 위상 정렬)
코딩하세현
2025. 2. 25. 17:34
728x90
(9) 그래프 응용 - 백트래킹
a) 해를 찾기 위해서 후보군을 나열하고, 만약 조건에 맞지 않다면 후보군에서 제외하고 돌아와 다음 후보군을 찾는 방식
백트래킹은 트리 구조를 기반으로 DFS 방식을 진행하면서 각 루트에 대해 조건에 부합했는지 체크(Promising)
만약 해당 트리에서 조건에 맞지 않는 노드를 발견한다면, 더 이상 탐색을 멈추고, 다른 노드로 가기 위해 현재 가지를 버림(Pruning)
백트래킹에서 검색할 후보들을 상태 공간 트리(State Space Tree)로 표현
8-Queens라면 8^8=16,000,000이
넘는 경우의 수를 확인해야 하는데 Pruning을 하면 약 4000~5000정도만 탐색하여 92개의 해를 얻게 됨
import java.util.LinkedList;
import java.util.List;
public class Jes_NQueens {
static int N = 4; // 4x4 체스판
static List<Position> promise = new LinkedList<>();
static int promiseSetCnt;
public static void main(String[] args) {
dfs(0); // 첫 번째 행부터 시작
System.out.println("result: " + promiseSetCnt);
}
static void dfs(int curRow) {
System.out.println("현재 행: " + curRow); // 현재 행 출력
if (curRow == N) { // N번만큼 돌았다면
promiseSetCnt++; // 완성된 세트를 카운트
System.out.println("=====>완성된 세트: " + promise); // 완성된 세트 출력
return;
}
for (int col = 0; col < N; col++) {
if (isSafe(curRow, col)) { // 이 위치가 유망하면
promise.add(new Position(curRow, col)); // 현재 위치를 유망목록에 넣는다
System.out.println("퀸 추가: " + promise); // 현재 유망 목록 출력
dfs(curRow + 1); // 다음 행으로 이동
promise.remove(promise.size() - 1); // 마지막으로 추가한 퀸을 제거
System.out.println("퀸 제거: " + promise); // 유망 목록에서 퀸 제거 후 출력
} else { //백트래킹
System.out.println("위치 안전하지 않음: (" + curRow + ", " + col + ")"); // 안전하지 않은 위치 출력
}
}
}
// 현재 위치에 퀸을 배치할 수 있는지 확인하는 메소드
static boolean isSafe(int curRow, int col) {
for (Position queen : promise) {
// 유망목록에 들어가 있는 퀸들과 열이 같으면 탈락
if (col == queen.col) return false;
// 유망목록에 들어가 있는 퀸들의 대각선(X2 - X1 = |Y1-Y2| )에 있으면 탈락
if (curRow - queen.row == Math.abs(col - queen.col)) return false;
}
return true; // 유망 위치
}
static class Position {
int row, col;
Position(int row, int col) {
this.row = row;
this.col = col;
}
@Override
public String toString() {
return "Position [" + row + "," + col + "]";
}
}
}
(10) 그래프 응용 - 위상정렬
위상 정렬(Topological Sorting)
방향 그래프의 정점들을 선형으로 배열하는 방법으로, 주로 의존성 문제에서 사용. 사이클이 없을 때만 가능
방법
1. 진입 차수 계산: 각 정점의 진입 차수(해당 정점으로 들어오는 간선의 수)를 계산합니다.
2. 큐에 추가: 진입 차수가 0인 정점을 큐에 추가합니다.
3. 정점 처리: 큐에서 정점을 하나씩 꺼내어 결과 리스트에 추가하고, 그 정점과 연결된 모든 정점의 진입 차수를 감소시킵니다. 만약 진입 차수가 0이 되는 정점이 있다면 큐에 추가합니다.
4. 결과 확인: 모든 정점을 처리했는지 확인합니다. 처리된 정점의 수가 원래 정점의 수와 같다면 위상 정렬이 성공한 것
/*
https://www.acmicpc.net/problem/1766
입력
4 2
4 2
3 1
출력
3 1 4 2
조건
1.N개의 문제는 모두 풀어야 한다.
2.먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3.가능하면 쉬운 문제부터 풀어야 한다.
*/
import java.util.*;
public class 위상정렬 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 문제 수(N)와 의존 관계 수(M) 입력
int N = sc.nextInt();
int M = sc.nextInt();
// 그래프를 위한 인접 리스트 초기화
List<List<Integer>> graph = new ArrayList<>(N + 1);
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>()); // 각 정점에 대해 빈 리스트 추가
}
// 진입 차수 배열 초기화
int[] inDegree = new int[N + 1];
// 의존 관계 입력 처리
for (int i = 0; i < M; i++) {
int a = sc.nextInt(); // 선행 문제
int b = sc.nextInt(); // 후행 문제
graph.get(a).add(b); // 그래프에 간선 추가
inDegree[b]++; // 후행 문제의 진입 차수 증가
}
// 위상 정렬을 위한 최소 힙(우선순위 큐) 초기화
//Queue<Integer> pq = new LinkedList<>();
//3번 조건때문에 pq로 해야 함
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 진입 차수가 0인 문제들을 큐에 추가
for (int i = 1; i <= N; i++) {
if (inDegree[i] == 0) {
pq.offer(i);
}
}
// 위상 정렬 결과를 저장할 리스트
List<Integer> result = new ArrayList<>();
// 큐가 비어있지 않을 때까지 반복
while (!pq.isEmpty()) {
int current = pq.poll(); // 큐에서 문제 하나 꺼내기
result.add(current); // 현재 문제를 결과 리스트에 추가
// 현재 문제에 의존하는 문제들에 대해
for (int neighbor : graph.get(current)) {
inDegree[neighbor]--; // 진입 차수 감소
if (inDegree[neighbor] == 0) { // 진입 차수가 0이 되면
pq.offer(neighbor); // 큐에 추가
}
}
}
// 결과 출력
for (int problem : result) {
System.out.print(problem + " "); // 문제 번호 출력
}
sc.close(); // 스캐너 닫기
}
}728x90