[알고리즘풀이]백준 2056 : 작업 JAVA

목차

• 개요
•  본문
•  1) 문제
•  2) 과정
•  3) 코드 전체

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 2056번 작업을 풀었습니다. 이를 정리해보고자 합니다.

2056번: 작업

 

본문

1) 문제

 

2) 과정

이번문제는 1시간 정도 걸려서 풀었던 문제입니다. 기본 틀이 머리에 생겨서 크게 어렵지 않게 풀었어요. 기본적인 위상정렬 문제에 Output만 신경써주면 됐어서 편리했습니다. 이번 문제의 아이디어 풀이는 위상정렬 풀이의 기본방식을 설명한다고해도 무방할 것 같네요 :)

참고로 위상정렬은 선행해야할 과제/문제/노드가 있을 경우에 진입차수가 없는 노드(indgree가 0인 노드)를 큐에 넣어 indegree를 줄여가며 모든 노드를 탐색하는 방법입니다.

 

제가 문제를 풀며 사용했던 아이디어는 다음과 같습니다.

1. indegree값과 진출노선들을 정리해야하는 게 Input에서 해야할 내용들이다.
2. 그 후에 진입차수(indeg)가 0인것을 먼저 모아 큐에 넣어주고
3. 큐에서 수를 하나(cur)빼서 그 노드를 진입노드로 생각하는 노드들(next)의 indegree값을 하나씩 빼내 연결을 끊어간다. 
4. 그러다 next의 indegree가 0이되면 q에 넣어 탐색을 수행함.
5. 모든 노드들의 indegree가 0이되고 탐색도 끝났다면 각 노드들의 총 소요시간(totalTime) 중 가장 큰 값을 출력

 

이번에 풀어본 문제들을 input, logic, output에 맞춰 나눠 보여드리고 빨리 마무리 짓겠습니다.. 설명은 주석으로 최대한 달아뒀어요!!

 

2-0) MyIO

    // Inner Class - Read & Write values
    private static class MYIO{
        // Variable
        BufferedReader br;
        StringTokenizer st;
        StringBuilder sb;
        // Constuctor
        public MYIO(){
            br = new BufferedReader(new InputStreamReader(System.in)); 
            sb = new StringBuilder();
        } 
        // Method - for input
        public void readLine() throws IOException{ st = new StringTokenizer(br.readLine());}
        public int nextInt(){ return Integer.parseInt(st.nextToken());}
        // Method - for output
        public void append(int i) {sb.append(i+"\n");}
        public String toString(){return sb.toString();}
    }

MyReader는 여러번 중첩되어 많이 사용되는 BufferedReader와 StringTokenizer, StringBuilder를 짧게 작성하여 사용하고자 만든 클래스입니다!

 

2-1) Input

    public static void main(String[] args) throws IOException {
        // Input
        MYIO io = new MYIO();
        io.readLine();
        int n = io.nextInt();
        // initialize array
        int[] delayArr = new int[n+1];
        int[] indeg = new int[n+1];
        ArrayList<Integer>[] outdeg = new ArrayList[n+1];
        for(int i=1;i<=n;i++){
            io.readLine();
            // save delay time
            delayArr[i] = io.nextInt();
            // make connection 
            for(int con = io.nextInt();con>0;con--){
                int prev = io.nextInt();
                if(outdeg[prev]==null) outdeg[prev] = new ArrayList<>();
                outdeg[prev].add(i);
                indeg[i]++;
            }
        }
    }

 

 

2-2) Logic & Output

    public static void main(String[] args) throws IOException {
        // Logic
        // find zero indegree
        int[] totalTime = new int[n+1]; // 각노드가 종료되기까지 걸리는 총 시간
        Queue<Integer> q = new ArrayDeque<>(); // 탐색을 위해 사용한 큐
        for(int i=1;i<=n;i++){
            // indegree값이 0이면 진입차선이 없다는 것이기 때문에 시작점으로 사용
            if(indeg[i]==0) {
                q.add(i);
                totalTime[i] = delayArr[i];
            }
        }
        // topological sort
        while(!q.isEmpty()){
            // get a number
            int cur = q.poll();
            // if outdeg == null (it means out-connection is not exist -> skip this loop)
            if(outdeg[cur]==null) continue;
            // for next
            for(int next : outdeg[cur]){
                // save cur's out-connection node's construction time
                totalTime[next] = Math.max(totalTime[next],totalTime[cur]+delayArr[next]);
                // subtract indegree value and add it into q if indegree eqals zero 
                if(--indeg[next]==0) q.add(next);
            }
        }
        // Output
        System.out.println(Arrays.stream(totalTime).max().getAsInt());
    }

 

 

 

3) 전체코드

그렇게 완성된 코드는 아래쪽에 링크된 깃헙 레포짓토리에 방문하여 확인해주세요!

소요시간, 아이디어, 에러로그 등 더 자세히 보실 수 있습니다.

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/topological_sort/BOJ2056.java

GitHub - Park1122/Algorithm-Study: 명지대학교 학생들이 모여서 만든 알고리즘 공부 및 코딩테스트 준비