백준 2252 줄 세우기(자바)

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

위상정렬을 처음 배우고 풀은 문제다.

위상정렬은 큐, 스택 두 가지 방법으로 구현이 가능한데 큐를 대부분 많이 사용한다고 해서 큐로 구현하였다.

 

위상정렬은 순서가 있는 작업을 차례로 진행해야 할 때 순서를 결정하기 위해 사용하는 알고리즘이다.

 

문제에서 가중치가 안 주어진 유향그래프고 사이클이 없으니 위상정렬로 문제를 접근했다.

 

우선 전체 코드를 살펴보자.

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		int[] inde = new int[V + 1];
		List<Integer>[] list = new ArrayList[V + 1];
		List<Integer> result = new ArrayList<>();
		for (int i = 0; i < V + 1; i++) {
			list[i] = new ArrayList<>();
		}

		for (int i = 0; i < E; i++) {
			int st = sc.nextInt();
			int ed = sc.nextInt();
			list[st].add(ed);
			inde[ed]++;
		}

		Queue<Integer> q = new LinkedList<Integer>();

		// 큐에 담을 거다.
		for (int i = 1; i < V + 1; i++) {
			if (inde[i] == 0) { // 해당 진입 차수가 0이면 큐에 담는다.
				q.add(i);
			}
		}

		while (!q.isEmpty()) {
			int curr = q.poll();
			result.add(curr);

			for (int i = 0; i < list[curr].size(); i++) {
				int temp = list[curr].get(i);
				inde[temp]--;
				if (inde[temp] == 0) {
					q.add(temp);
				}
			}
		}
		
		for(int i=0; i<result.size(); i++) {
			if(result.get(i)!=0) {
				System.out.print(result.get(i)+" ");
			}
		}

	}
}

큐를 사용하는 방법을 택했으니 큐로 문제를 풀어보겠다~!

 

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int V = sc.nextInt();
		int E = sc.nextInt();
		int[] inde = new int[V + 1];
		List<Integer>[] list = new ArrayList[V + 1];
		List<Integer> result = new ArrayList<>();
		for (int i = 0; i < V + 1; i++) {
			list[i] = new ArrayList<>();
		}

우선 정점과 간선을 입력받고

inde(진입 차수를 표시 할 배열)을 선언했다.

그리고 간선의 정보를 저장할 list와 결과를 담을 result를 만들어주었다.

for문을 돌면서 list배열 각각에 리스트를 생성해준다.

 

for (int i = 0; i < E; i++) {
	int st = sc.nextInt();
	int ed = sc.nextInt();
	list[st].add(ed);
	inde[ed]++;
}

간선의 개수만큼 for문을 돌면서 시작 정점, 도착 정점을 입력 받고

유향 그래프니 list에 하나만 넣어준다.

inde[ed]++을 하는 이유는 도착 정점에 진입하는 간선의 개수를 표시하기 위해 1씩 더해준다.

 

Queue<Integer> q = new LinkedList<Integer>();

// 큐에 담을 거다.
for (int i = 1; i < V + 1; i++) {
	if (inde[i] == 0) { // 해당 진입 차수가 0이면 큐에 담는다.
		q.add(i);
	}
}

큐를 우선 생성해주고 

위상정렬은 진입차수가 0일때 보기 때문에 inde[i]번이 0이면 큐에다 넣어준다.

 

while (!q.isEmpty()) {
	int curr = q.poll();
	result.add(curr);

	for (int i = 0; i < list[curr].size(); i++) {
		int temp = list[curr].get(i);
		inde[temp]--;
		if (inde[temp] == 0) {
			q.add(temp);
		}
	}
}

큐가 들어있으면 while문을 돌 건데

curr에 q를 빼서 담을 거다.(현재 q에는 1,2 순으로 담겨있었다)

curr을 result에 다시 넣어준다.

 

이후에 curr번 리스트에 있는 사이즈(개수)만큼 for문을 돌면서

temp에 i를 뽑아서 저장한다.(temp는 결국 curr과 연결된 도착 정점이 된다.)

골랐으니 진입 차수를 1 빼준다.

이후에 inde[temp]를 확인해서 0이면 큐에 넣을 준비가 되었다는 소리니 큐에 집어넣어준다.

 

for(int i=0; i<result.size(); i++) {
	if(result.get(i)!=0) {
		System.out.print(result.get(i)+" ");
	}
}

그러고 result를 뽑아냈을 때 0이 아니면 출력해주면 된다.