백준 1766. 문제집

🅰 백준 1766. 문제집

1766번: 문제집

✏️ 문제 풀이

• 백준 2252 줄 세우기 문제랑 99% 동일한 문제이다. 다른점이란 가능하면 쉬운 문제를 먼저 풀어야 한다는 조건이 하나 더 생겼을 뿐이다. 이를 해결하기 위해서는 queue대신 PriorityQueue를 사용하여 들어오는 정점들을 오름차순으로 저장해서 순서대로 탐색하면 된다는 점이다.
• 아래에는 2252 줄 세우기 문제랑 해설이 동일하다.
• 위상정렬이란 그래프의 개념과 큐를 이용하여 푸는 것으로, 어떤 일을 하는 순서를 찾는 알고리즘이다. 중요한 것은 큐에 넣을 때 연결된 간선이 하나밖에 없는 정점만 넣어줘야 한다는 것이다.
• 먼저 인접리스트, 큐, 연결된 간선 수를 체크해줄 check배열을 선언하였다.
• 먼저 그래프를 생성하기 위해 인접리스트를 생성해주고, A와 B 학생의 우선순위를 받아 A의 리스트에 B를 저장한다
• 그다음 들어오는 간선이 생긴 B를 check[B]++ 하여 들어오는 총 간선수를 체크해준다.
• 그 후 PriorityQueue에 check배열을 N만큼 탐색을 하여 들어오는 간선의 개수가 없는 정점을 저장해준다.
• PriorityQueue가 비어있을때 까지 반복하여 탐색하면서 나온 정점(cur)을 StringBuilder에 저장해주고, cur에 연결된 간선들을 하나씩 탐색해주면서 만약 정점이 들어오는 간선이 cur 하나밖에 없다면 PriorityQueue에 저장해주고 아니면 pass한다.
• 그 후 check[to] -- 를 통해 cur과 연결된 간선들의 수를 다 빼준다.

✏️ 소스코드

package graph;

import java.util.*;
import java.io.*;

public class Main_골드2_1766_문제집 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
		Queue<Integer> queue = new LinkedList<Integer>();
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		for (int i = 0; i <= N; i++) { // 인접리스트 초기화
			list.add(new ArrayList<>());
		}
		int check[] = new int[N + 1];
		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			list.get(A).add(B); // 인접리스트에 저장
			check[B]++; // 들어오는 간선 수 ++
		}

		for (int i = 1; i <= N; i++) { // 들어오는 간선의 개수가 0인 것들 queue에 저장
			if (check[i] == 0) {
				queue.add(i);
			}
		}

		while (!queue.isEmpty()) {
			int cur = queue.poll();
			sb.append(cur + " ");
//							현재 cur에 연결된 리스트 사이즈 만큼 탐색
			for (int i = 0, end = list.get(cur).size(); i < end; i++) {
				int to = list.get(cur).get(i);	// 하나씩 탐색
				if (check[to] == 1) {	// 만약 들어오는 간선이 cur 하나 뿐이라면
					queue.add(to);	// queue에 저장
				}
				check[to]--;	// 연결된 간선 제거
			}
		}
		System.out.println(sb);
	}
}

 

✅ 후기

•