[백준] 알고리즘 분류(그래프 이론,JAVA)1766번, 문제집

문제 링크

1766번: 문제집

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 민오는 문제를 푸는 것에 3가지 조건에 만족하는 순서로 풀어야 합니다.

2. 문제의 난이도는 1번부터 N번까지 오름차순입니다.

3. 민오가 조건에 만족하도록 모든 문제를 푸는 순서를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

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

 

2. 위상 정렬을 통해서 모든 문제를 풀 수 있도록 탐색합니다.

 

3. 모든 문제를 풀었을 때 순서를 결과로 출력합니다.

 

각 지역 최단 거리 탐색!

 

 

위상 정렬을 통해서 조건에 맞게 모든 문제를 푸는 순서를 구합니다.

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

 

 

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

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

 

child가 0일 때 문제을 풀이 가능!

 

Why?

 

해당 문제을 가리키는 선행 문제들이 모두 해결되었다고 판단할 수 있기 때문입니다.

 

{3, 5, 7} 건물 완공!

 

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

 

{8, 9} 건물 완공!

 

 

....

 

이러한 방식으로 문제를 풀어가며 모든 문제를 풀었을 때 순서를 결과로 출력하면 됩니다.

 

 

예제입력 1.

 

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

 

N : 4

M : 2

 

건물 완공 시간 : { 4, 2 }, { 3, 1 }

 

문제 관계 정보

 

	1	2	3	4
child	1	1	0	0

 

2. 위상 정렬을 통해서 모든 문제를 풀 수 있도록 탐색합니다.

 

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

child 0 : { 3, 4 } 

 

3번 문제 풀기

 

 

	1	2	3	4
child	0	1	0	0

child 0 : { 1, 4 } 

1번 문제 풀기

 

	1	2	3	4
child	0	1	0	0

child 0 : { 4 } 

4번 문제 풀기

	1	2	3	4
child	0	0	0	0

child 0 : { 2 } 

2번 문제 풀기

모든 문제 풀기 성공!

 

3. 모든 문제를 풀었을 때 순서를 결과로 출력합니다.

 

모든 문제 풀이 순서 : 3 - 1 - 4 - 2

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

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 문제 관련된 정보들을 띄어쓰기 기준 나누었습니다.
• 위상 정렬을 이용하여 문제를 푸는 과정을 탐색합니다.
• 모든 문제를 풀었을 때 순서를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

결과코드

package com.ssafy.bacjoon;

import java.io.*;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
    //문제간 관계를 연결하는 정보 저장하는 리스트
    static ArrayList<ArrayList<Integer>> graph  = new ArrayList<>();
    //선행 문제 개수 저장 배열
    static int[] count;
    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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        for(int i=0;i<=N;i++)
            graph.add(new ArrayList<>());
        count = new int[N+1];
        //입력되는 문제 선행관계 저장
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine()," ");
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            graph.get(A).add(B);	//A는 B의 선행문제이다.
            count[B]++;	//B의 선행문제 개수 증가
        }
        //난이도가 쉬운 것부터 탐색하기 위해 우선순위 큐 사용
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        //선행 문제가 없는 문제들 우선순위 큐에 저장
        for(int i=1;i<=N;i++)
            if(count[i] == 0)	//선행 문제가 없을 때
                pq.offer(i);
        //위상 정렬을 이용한 문제들 탐색
        while(!pq.isEmpty()) {
            int cur = pq.poll();	//현재 문제 풀기 완료
            sb.append(cur).append(" ");	//현재 문제 StringBuilder 저장
            //현재 문제를 풀면 이어지는 문제들 탐색
            for(int nxt : graph.get(cur)) {
                count[nxt]--;
                if(count[nxt] == 0)	//이어지는 문제도 선행문제를 다 풀었을 경우
                    pq.add(nxt);
            }
        }
        bw.write(sb.toString());	//문제 풀이 순서 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();


    }
}