[URECA] Day22 | 알고리즘 | 그래프 응용(백트래킹, 위상 정렬)

(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.geeksforgeeks.org/topological-sorting/

 

/*
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(); // 스캐너 닫기
    }
}