[ 백준 2252번 줄 세우기 ] 문제 풀이(Java) - 위상 정렬 문제 풀이

 

백준에서 '그래프 이론' 카테고리에 있는 문제를 살펴보다가 해당 문제를 보게 되었습니다.

어떻게 풀어야할지 방법이 떠오르지 않아 구글에서 다른 분들의 풀이를 보게 되었는데, 위상 정렬이라는 정렬 방식을 이용하는 문제였습니다.

(이전에 알고리즘 시간에 위상 정렬 배운거 같긴 한데,,,, 기억이 나지 않아서 개념부터 다시 봤습니다 ㅋㅋ)

 

 

문제 보기

www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

나의 풀이

 

이 문제는 정확하게 위상 정렬(Topology Sort)에 대해 알아야 풀 수 있습니다.

위상 정렬에 대해 모르시거나 생소하신 분들은 다음 유투브 영상보는 것을 추천합니다!

m.blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)

 

위상 정렬은 '순서가 정해져 있는 요소'들을 정렬할 때 사용하는 정렬 방식입니다. 일반적으로 사이클이 존재하는 그래프는 위상 정렬이 불가합니다. 왜냐하면 위상 정렬에서는 진입 차수가 0인 시작점을 찾는 것이 중요한데, 사이클이 존재하게 되면 시작점을 찾는 것이 불가하기 때문이죠.

 

알고리즘은 다음과 같습니다.

 

1. 진입 차수가 0인 정점들을 큐(Queue)에 넣는다.

2. 큐에서 차례로 정점을 꺼내며 해당 정점의 간선을 제거한다. (진입 차수 배열 업데이트)

   (여기서 진입 차수가 0이 된 지점은 큐에 넣어주어야 한다.)

3. n개의 요소를 큐에서 다 꺼낼 때 까지 위 과정을 반복한다.

 

개념만 알면 어렵진 않은데, 아무래도 개념을 모르시는 분들이 많아서 난이도가 높게 측정이 되어있는거같네요. (저처럼..)

 

 

코드

//백준 2252번 줄 세우기
//위상정렬(Topology Sort)

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class N_2252 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		int N = Integer.parseInt(input[0]); // 정점의 개수
		int M = Integer.parseInt(input[1]); // 간선의 개수

		int[] indegree = new int[N + 1]; // 각 정점의 진입 차수 저장
		ArrayList<Integer>[] adlist = (ArrayList<Integer>[]) new ArrayList[N + 1]; // 간선 저장
		for (int i = 1; i <= N; i++)
			adlist[i] = new ArrayList<Integer>();

		for (int i = 0; i < M; i++) {
			String[] arr = br.readLine().split(" ");
			adlist[Integer.parseInt(arr[0])].add(Integer.parseInt(arr[1]));
			indegree[Integer.parseInt(arr[1])]++;
		}

		// 위상 정렬
		Queue<Integer> q = new LinkedList<Integer>();
		for (int i = 1; i <= N; i++) { // 진입 차수가 0인 정점 큐에 넣기
			if (indegree[i] == 0)
				q.offer(i);
		}

		for (int i = 1; i <= N; i++) { // 큐에서 n번 꺼내면 위상정렬 완료!
			int vertex = q.poll();
			System.out.print(vertex + " ");

			for (int j = 0; j < adlist[vertex].size(); j++) {
				indegree[adlist[vertex].get(j)]--;
				if (indegree[adlist[vertex].get(j)] == 0)
					q.offer(adlist[vertex].get(j));
			}
		}
	}

}