[알고리즘풀이]백준 1005 : ACM Craft JAVA

목차

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

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 1005번 ACM Craft를 풀었습니다. 이를 정리해보고자 합니다.

1005번: ACM Craft

 

본문

1) 문제

2) 과정

이 문제를 푸는데는 5시간 정도가 소요되었고 에러 없이 통과한 문제였습니다.

 

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

1. 입력
   1. 테스트케이스의 수를 입력받아 그만크 for문 내부를 반복한다.
   2. 값을 읽어 지연시간을 delayArr에 담고, 진출차선으로 연결되는 노드들을 담은 entArr을 만들어줍니다.
   3. 진입차선의 수를 세며 entArr을 채워줍니다.
2. 로직
   1. 진입차선이 없는 노드들을 큐에 담고, 그 노드들까지의 걸리는 시간(timeArr[i])을 그 노드가 갖는 지연시간으로 설정하여 넣어줍니다.
   2. 큐가 빌때까지 다음노드에 도달하기 위해 걸리는 시간을 계산하고, 다음노드의 진입차수가 0이되어 다음 노드에 도달할 수 있는 상태가 되면 큐에 넣어 탐색을 계속합니다.
3. 출력
   1. 승리를 위해 건설해야할 건물의 번호를 입력받아 해당 건물의 소요시간(timeArr)을 StringBuilder를 통해 담습니다.
   2. 모든 테스트 케이스를 다 돈 뒤 StringBuilder에 저장된 값들을 출력합니다.

 

이번에 풀어본 문제들을 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

    private static int n,k;
    private static int[] indeg, delayArr, timeArr;
    private static ArrayList<Integer>[] entArr;

    public static void main(String[] args) throws IOException{
        // Input & Initialize
        MyIO mr = new MyIO();
        mr.readLine();
        for(int T=mr.nextInt();T>0;T--){
            // read value
            mr.readLine();
            n=mr.nextInt(); // 건물의 개수 (1~n)
            k=mr.nextInt(); // 건물간의 건설순서 규칙의 총 개수
            // initialize arrays
            delayArr = new int[n+1];
            entArr = new ArrayList[n+1];
            indeg = new int[n+1];
            // read delay time and initialize entArr
            mr.readLine();
            for(int i=1;i<=n;i++){
                delayArr[i] = mr.nextInt();
                entArr[i] = new ArrayList<>();
            }
            // read connection information and count indegree nodes
            for(int i=0;i<k;i++){
                mr.readLine();
                int x = mr.nextInt();
                int y = mr.nextInt();

                entArr[x].add(y);
                indeg[y]++;
            }
        }
    }

 

 

2-2) Logic

     private static void logic(){
        // initalize
        Queue<Integer> q = new ArrayDeque<>();
        timeArr = new int[n+1];
        // find start Node(indeg==0) and initialize their arrival time
        for(int i=1;i<=n;i++){
            if(indeg[i]==0) {
                q.add(i);
                timeArr[i] = delayArr[i];
            }
        }
        // searching
        while(!q.isEmpty()){
            // get a number
            int num = q.poll();
            // for next
            for(int next : entArr[num]){
                // next Node에 도달하기 위해 걸리는 시간 계산
                timeArr[next] = Math.max(timeArr[next],timeArr[num]+delayArr[next]);
                // next Node에 도달할 수 있는 상태가 되면(indeg==0) 큐에 넣어 탐색할 수 있게함.
                if(--indeg[next]==0) q.add(next);
            }
        }
    }

 

2-3) Output

    public static void main(String[] args) throws IOException{
        for(int T=mr.nextInt();T>0;T--){
            // Output
            mr.readLine();
            mr.append(timeArr[mr.nextInt()]);
        }
        // Final Output
        System.out.println(mr.toString());
    }

 

3) 전체코드

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

앞서 말씀드렸듯이 소요시간, 아이디어, 에러로그 등 더 자세히 보실 수 있습니다.

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

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