[ Java] 1766번 : 문제집

문제 풀이

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

해당 문제를 쉽게 이해하기 위해 이전 포스트([알고리즘] 위상 정렬 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());
    }

}

SSAFY10-Class5-Algorithm / BOJ

[ Java] 1766번 : 문제집 #55

문제 풀이