[ Java] 1766번 : 문제집

[peppermintt0504]

문제 풀이

해당 문제는 위상 정렬을 통해 문제 풀이 순서를 구하는 문제이다. 이 때 단순 위상 정렬이 아닌 최대한 난이도가 쉬운 문제를 먼저 풀도록 문제 순서를 정해야 한다.

해당 문제를 쉽게 이해하기 위해 이전 포스트([알고리즘] 위상 정렬 Topological Sort)를 참조하면 좋을 것 같다.

문제에서 주어지는 '먼저 풀어야 하는 문제'를 입력 받고, 먼저 풀어야 하는 문제를 가지는 문제를 저장하고, indegree(코드에서는 Need)로 카운팅한다.

public static Map<Integer,Problem> memo = new HashMap<>();
	
public static class Problem implements Comparable<Problem>{
    int no;
    ArrayList<Integer> pre = new ArrayList<>();
    int need = 0;

    public Problem() {

    }

    public Problem(int no) {
        this.no = no;
    }

    public void addPre(int no) {
        pre.add(no);
    }
    public void removePre(int no) {
        pre.remove(pre.indexOf(no));
    }

    public void addNeed() {
        need++;
    }
    public void removeNeed() {
        need--;
    }

    @Override
    public int compareTo(Problem o) {
        // TODO Auto-generated method stub
        return this.no - o.no;
    }
    @Override
    public String toString() {
        return "[no : "+Integer.toString(this.no) + ", priority : " + this.pre.toString() +"]";
    }
}

public static void main(String[] args) throws IOException{
    st = new StringTokenizer(br.readLine());

    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    for(int i = 1; i <= N; i++) {
        memo.put(i, new Problem(i));
    }

    for(int i = 0; i < M; i++) {
        st = new StringTokenizer(br.readLine());

        int f = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        memo.get(f).addPre(n);
        memo.get(n).addNeed();
    }

    ....
        
}

이 후 우선순위 큐를 생성하고, 해당 큐에 먼저 풀어야 하는 문제를 가지고 있지 않는 문제를 추가해준다.

PriorityQueue<Problem> qu = new PriorityQueue<>();

for(int i = 1 ; i <= N; i++) {
    Problem temp = memo.get(i);
    if(temp.need == 0) {
        qu.add(temp);
    }
}

이제 해당 우선순위 큐를 순회하며 해당 문제를 먼저 풀어야 하는 문제로 가지고 있는 문제의 indegree를 줄여나가며 indegree가 0이 될 경우 우선순위 큐에 추가하여 문제 순서를 주어진 조건(쉬운 문제를 먼저 풀기)를 충족시키며 문제 순서를 만들어 나가면 된다.

while(!qu.isEmpty()) {
    Problem cur = qu.poll();
    sb.append(cur.no + " ");
    for(int next : cur.pre) {
        memo.get(next).removeNeed();
        if(memo.get(next).need == 0) {
            qu.add(memo.get(next));
        }
    }

}

풀이 코드

import java.util.*;
import java.io.*;


public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static StringTokenizer st;
	public static StringBuilder sb = new StringBuilder();
	public static int INF = 100_000_000;
	public static int[] dx = {0,1,0,-1};
	public static int[] dy = {-1,0,1,0};
	
	public static Map<Integer,Problem> memo = new HashMap<>();
	
	public static class Problem implements Comparable<Problem>{
		int no;
		ArrayList<Integer> pre = new ArrayList<>();
		int need = 0;
		
		public Problem() {
			
		}
		
		public Problem(int no) {
			this.no = no;
		}
		
		public void addPre(int no) {
			pre.add(no);
		}
		public void removePre(int no) {
			pre.remove(pre.indexOf(no));
		}
		
		public void addNeed() {
			need++;
		}
		public void removeNeed() {
			need--;
		}
		
		@Override
		public int compareTo(Problem o) {
			// TODO Auto-generated method stub
			return this.no - o.no;
		}
		@Override
		public String toString() {
			return "[no : "+Integer.toString(this.no) + ", priority : " + this.pre.toString() +"]";
		}
	}

	public static void main(String[] args) throws IOException{
		st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		for(int i = 1; i <= N; i++) {
			memo.put(i, new Problem(i));
		}
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			
			int f = Integer.parseInt(st.nextToken());
			int n = Integer.parseInt(st.nextToken());
			
			memo.get(f).addPre(n);
			memo.get(n).addNeed();
		}
		
		
		PriorityQueue<Problem> qu = new PriorityQueue<>();

		for(int i = 1 ; i <= N; i++) {
			Problem temp = memo.get(i);
			if(temp.need == 0) {
				qu.add(temp);
			}
		}
		

		while(!qu.isEmpty()) {
			Problem cur = qu.poll();
			sb.append(cur.no + " ");
			for(int next : cur.pre) {
				memo.get(next).removeNeed();
				if(memo.get(next).need == 0) {
					qu.add(memo.get(next));
				}
			}

		}
		System.out.println(sb.toString().trim());
	}
	
	
}