[백준] 알고리즘 분류(그래프 이론,JAVA)2252번, 줄 세우기

문제 링크

2252번: 줄 세우기

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 주어진 두 학생에 대해서는 키의 대한 비교가 이루집니다.

2. 키를 순서대로 세웠을 경우를 결과로 출력합니다.

3. 답이 여러가지인 경우 아무거나 출력해도 상관없습니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 위상 정렬을 통해서 모든 학생이 순서대로 세우는 경우를 탐색합니다.

 

3. 탐색이 끝난 뒤 줄을 선 순서대로 결과로 출력합니다.

 

줄 세우기 탐색!

 

 

위상 정렬을 통해서 학생이 현재 줄을 설 수 있는지을 확인합니다.

위상정렬 - 위키백과, 우리 모두의 백과사전

 

 

예를 들어 아래와 같은 상황일 때

	2	3	5	7	8	9	10	11
앞 학생	1	0	0	0	2	2	2	2

 

 

앞 학생이 0일 때 줄을 설 수 있습니다.

 

Why?

 

해당 학생보다 작은 학생들이 모두 줄에 포함되었다고 판단할 수 있기 때문입니다.

 

{3, 5, 7} 줄 세우기 완료!

 

	2	3	5	7	8	9	10	11
child	1	0	0	0	0	2	0	3

 

{8, 9} 줄 세우기 완료!

 

 

....

 

이러한 방식으로 학생들을 줄 세우며 모든 학생이 줄을 섰을 때 줄에 대한 정보를 결과로 출력하면 됩니다.

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N : 3

M : 2

 

 

학생 관계 정보

 

	1	2	3
앞 학생	0	0	2

 

2. 위상 정렬을 통해서 모든 학생이 순서대로 세우는 경우를 탐색합니다.

 

 

위상 정렬을 이용한 탐색 진행!

 

앞 학생 0 : { 1, 2 } 

 

1번 학생과 2번 학생 줄세우기 성공!

 

1 ▶ 2

 

	1	2	3
앞 학생	0	0	0

 

child 0 : { 3 } 

 

3번 학생 줄 세우기 성공!

 

1 ▶ 2 ▶ 3

 

	1	2	3
앞 학생	0	0	0

 

모든 학생 줄세우기 성공!

 

 

3. 탐색이 끝난 뒤 줄을 선 순서대로 결과로 출력합니다.

 

 

줄을 선 순서

 

1 ▶ 2 ▶ 3

 

1 2 3결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 학생들에 대한 정보를 띄어쓰기 기준 나누었습니다.
• 위상 정렬을 이용하여 각 학생이 줄을 서는 순서를 탐색합니다.
• 탐색이 종료되었을 때 현재 줄의 정보를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

결과코드

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		//입력값 처리하는 BufferedReader
        	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//결과값 출력하는 BufferedWriter
        	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[] count = new int[N+1];	//각 학생의 앞 학생 수 저장 배열
		ArrayList<ArrayList<Integer>> rel = new ArrayList<>();	//각 학생 비교 정보 저장
        	for(int i=0;i<=N;i++)
			rel.add(new ArrayList<>());
		
        	//비교 정보 저장 및 앞 학생 개수 세기
        	for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			rel.get(A).add(B);	//비교 정보 저장
			count[B]++;	//개수 증가
		}
		StringBuilder answer = new StringBuilder();
		Queue<Integer> q = new LinkedList<>();
		//앞 학생이 필요없는 학생들 모두 Queue 저장
        	for(int i=1;i<=N;i++) {
			if(count[i] == 0)	//앞 학생이 없는 경우
				q.add(i);
		}
       		//위상 정렬 탐색 진행!
		while(!q.isEmpty()) {
			int cur = q.poll();
			answer.append(cur).append(" ");
		//비교한 학생을 탐색!
            	for(int next : rel.get(cur)) {
				count[next]--;	//앞 학생이 줄에 포함되었으므로 - 1
				if(count[next] == 0)	//앞 학생 모두 줄에 포함되어서 줄 서기 가능!
					q.add(next);
			}
		}
		bw.write(answer.toString());	//줄을 선 결과 BufferedWriter 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();

	}
}