[#22] 백트래킹 + 위상 정렬

백트래킹

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

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

 

👩🏻‍💻 문제 풀어보기: N-Queens

package graph;

import java.util.LinkedList;
import java.util.List;

public class 백트래킹_NQueens {
	static int N = 4;
	static List<Position> promise = new LinkedList<>();
	static int promiseSetCnt;
	public static void main(String[] args) {
		dfs(0);
		System.out.println(promiseSetCnt);

	}

	static void dfs(int curRow) {
		if(curRow == N) {
			promiseSetCnt++; // 완성된 세트를 카운트
			return;
		}
		for (int col = 0; col < N; col++) {
			if (isSafe(curRow, col)) { // 이 위치가 유망하면
				promise.add(new Position(curRow, col));
				dfs(curRow + 1);
				promise.remove(promise.size()-1); // 백트래킹: 마지막으로 추가한 퀸 제거
			}

		}
	}

	static boolean isSafe(int curRow, int col) {
		for (Position queen : promise) {
			// 유망 목록에 들어가 있는 퀸들과 열이 같으면 탈락
			if (col == queen.col) return false;
			// 유망 목록에 들어가 있는 퀸들의 대각선(|X1 - X2| = |Y1 - Y2|)에 있으면 탈락
			if (Math.abs(queen.row - curRow) == Math.abs(queen.col - col)) return false;

		}
		return true;
	}

	// 퀸의 위치를 담고 있는 클래스
	static class Position {
		int row, col;

		public Position(int row, int col) {
			super();
			this.row = row;
			this.col = col;
		}

		@Override
		public String toString() {
			return "Position [row=" + row + ", col=" + col + "]";
		}

	}
}

• 시간복잡도: O(n!)
  • 8-Queens라면 8^8 = 16,000,000이 넘는 경우의 수를 확인해야 하는데 Pruning을 하면 약 4000 ~ 5000 정도만 탐색하여 92개의 해를 얻게 됨.

 

🍔 부분 집합으로 구현한 햄버거 다이어트 문제를 백트래킹 해보기

/*
	입력
	1
	5 1000
	100 200
	300 500
	250 300
	500 1000
	400 400
	
	출력
	#1 750
*/

package 순조부;

import java.util.Scanner;

public class SWEA_햄버거다이어트_백트래킹 {
	static int N, L;
	static int[] tastes, cals;
	static boolean[] isSelected;
	static int result;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt(); // 재료의 수
			L = sc.nextInt(); // 기준 총 칼로리

			tastes = new int[N];
			cals = new int[N];

			isSelected = new boolean[N];

			for (int i = 0; i < N; i++) {
				tastes[i] = sc.nextInt(); // 각 재료의 맛 점수
				cals[i] = sc.nextInt(); // 각 재료의 칼로리
			}

			result = 0;

			subset(0, 0, 0);
			sb.append("#").append(tc).append(" ").append(result).append("\n");
		}

		System.out.println(sb);
		sc.close();

	}

	private static void subset(int cnt, int tastesSum, int calsSum) {
		// 백트래킹
		if (calsSum > L) { // 칼로리 합이 기준 칼로리를 넘어버리면 이 결과 집합 세트는 버림
			return;
		}

		if (cnt == N) {
			result = Math.max(tastesSum, result);
			return;
		}

		subset(cnt + 1, tastesSum + tastes[cnt], calsSum + cals[cnt]);

		subset(cnt + 1, tastesSum, calsSum);

	}

}

 

위상 정렬(Topological Sorting)

방향 그래프의 정점들을 선형으로 배열하는 방법으로, 주로 의존성 문제에서 사용

• 사이클이 없을 때만 가능

출처: https://www.geeksforgeeks.org/topological-sorting/

 

위상 정렬 방법

1. 진입 차수 계산: 각 정점의 진입 차수(해당 정점으로 들어오는 간선의 수)를 계산
2. 큐에 추가: 진입 차수가 0인 정점을 큐에 추가
3. 정점 처리: 큐에서 정점을 하나씩 꺼내 결과 리스트에 추가하고, 그 정점과 연결된 모든 정점의 진입 차수를 감소시킴. 만약 진입 차수가 0이 되는 정점이 있다면 큐에 추가
4. 결과 학인: 모든 정점을 처리했는지 확인. 처리된 정점의 수가 원래 정점의 수와 같다면 위상 정렬이 성공한 것

 

👩🏻‍💻 문제 풀어보기: 백준_문제집_1766

/* 위상 정렬 */

/*
	입력
	4 2
	4 2
	3 1
	
	출력
	3 1 4 2
	
	조건
	1.N개의 문제는 모두 풀어야 한다.
	2.먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
	3.가능하면 쉬운 문제부터 풀어야 한다.
*/

package graph;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class 백준_문제집_1766 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		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]++; // 후향 문제의 진입 차수 증가
		}
		
		// 위상 정렬을 위한 최소 힙(우선순위 큐) 초기화
		// 3번 조건 때문에 pq로 해야 함
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		
		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 n:graph.get(current)) {
				inDegree[n]--; // 진입 차수 감소
				if(inDegree[n] == 0) { // 진입 차수가 0이 되면
					pq.offer(n); // 큐에 추가
				}
			}
		}

		for(int problem: result) {
			System.out.print(problem + " ");
		}
		
		sc.close();
	}

}