[백준 / Java] 2252번: 줄 세우기 (골드3)

문제 풀이 날짜: 2023.08.21
포스트 작성일: 2023.08.23

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 2252번: 줄 세우기 (골드3)

 

키워드

위상 정렬, BFS (너비 우선 탐색)

 

풀이 접근법

• 일부의 우선순위를 알고 있는 문제 ⇒ 위상 정렬을 활용하여 풀 수 있다.
• 위상정렬은 DFS와 BFS 모두로 구현할 수 있다. 이 포스트에서는 BFS로 구현한 방식을 사용한다.
  • degree 배열로 각 노드마다의 진입간선 수를 저장한다.
  • 처음에는 진입간선 수가 0인 노드부터 시작하여, 다른 노드를 방문할 때마다 진입간선의 수를 1씩 줄인다.
  • 진입간선의 수가 0이 된다면 그 노드를 큐에 넣고 다시 탐색해나간다.

 

코드

import java.util.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	private static int N;
	private static int M;
	
	private static int[] degree;
	private static boolean[] visited;
	private static List<Integer>[] graph;
	
	private static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] temp = br.readLine().split(" ");

		N = Integer.parseInt(temp[0]);
		M = Integer.parseInt(temp[1]);
		
		degree = new int[N + 1]; //0은 사용 안 함
		visited = new boolean[N + 1];
		graph = new LinkedList[N + 1];
		
		for(int i = 0; i < N + 1; i++) {
			graph[i] = new LinkedList<>();
		}
		
		for(int i = 0; i < M; i++) {
			temp = br.readLine().split(" ");
			
			int v = Integer.parseInt(temp[0]);
			int u = Integer.parseInt(temp[1]); 
			
			graph[v].add(u);
			degree[u]++;
		}
		
		topologicalSort();
		
		System.out.println(sb);
	}
	
	public static void topologicalSort() { //BFS
		Queue<Integer> queue = new ArrayDeque<>();
		
		for(int i = 1; i < N + 1; i++) {
			if(degree[i] == 0) {
				queue.add(i);
			}
		}
		
		while(!queue.isEmpty()) {
			int v = queue.poll();
			sb.append(v).append(" ");
			
			for(int u : graph[v]) {
				degree[u]--;
				
				if(degree[u] == 0) {
					queue.add(u);
				}
			}
		}
		
		return;
	}
}

---

 

 

git 링크

(git 링크 첨부)