[백준 2252] 줄 세우기 (자바)

 

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

2252번: 줄 세우기

난이도 : 골드 2

 

위상 정렬을 통해 풀 수 있는 문제입니다.

위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 사용할 수 있는 알고리즘입니다.

 

위상 정렬 설명을 위해 입학부터 졸업까지의 예시를 들어봤습니다.

물론 기사 신청에는 기능사 자격증이 필요없습니다.

 

'입학' -> '1학년' -> '2학년' -> '기능사 자격증' -> '3학년' -> '4학년' -> 기사 신청 -> '기사 자격증' -> '졸업' 등

여러 가지 순서도가 나올 수 있습니다.

 

각 행위마다 조건을 먼저 제거해줘야 합니다.

'입학'의 조건의 개수는 0, '3학년'의 조건의 개수는 1, '기사 신청'의 조건의 개수는 2입니다.

 

졸업을 하기 위한 과정을 예로 들어보겠습니다.

 

졸업까지는 후략하겠습니다.

 

이 과정을 저희는 배열, 리스트, 큐를 이용해볼 것입니다.

배열은 각 노드마다의 조건의 개수를 저장하고, 리스트는 연결 상태를 저장합니다.

큐는 조건의 개수가 0인 노드를 찾아 들어가 연결된 노드들의 조건 개수를 1씩 감소시킬 것입니다.

만약 연결된 노드의 조건 개수가 0이라면 큐에 넣고 반복합니다.

---

메소드

void main

list = 노드의 연결 상태를 저장

link = 조건의 개수를 저장

 

b의 앞에는 a가 와야 합니다. '2학년'이 되기 전 '1학년'을 거쳐야 합니다.

list[a]에 b를 연결하고 link[b]를 1 증가시킵니다.

 

모든 입력을 받은 후 조건이 0 ('입학')인 노드를 큐에 넣습니다.

이제 큐에 있는 노드들과 연결된 값들의 조건을 1씩 감소시켜줍니다.

'1학년'과 '기능사 자격증'이 되겠네요.

그리고 저 둘의 조건 값이 0이 되므로 큐에 넣어줍니다.

이 동작을 반복하면 위상 정렬을 완료할 수 있습니다.