[알고리즘풀이]백준 1516 : 게임 개발 JAVA

목차

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

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 1516번 게임 개발을 풀었습니다. 이를 정리해보고자 합니다.

1516번: 게임 개발

 

본문

1) 문제

 

2) 과정

이 문제를 먼저 풀었다가 1015번 문제와 비슷해서 1시간 만에 빠르게 풀었던 문제입니다. 

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

 

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

1. indegree가 0인 노드들을 큐에 담는다.
2. q로 부터 노드번호를 가져와 해당 노드로부터 연결되는(해당 노드를 진입노드로 생각하는) 노드들을 가져오며
3. 그 노드들의 총 건설시간(timeArr[next])을 새로운 건설기간(timeArr[cur]+delayArr[next])과 비교하며 업데이트해나간다.
4. 그 노드들의 진입차수가 3을 통해 0이된다면 큐에 담아 탐색할 수 있도록 하여 2~4를 반복한다.
5. 각 노드들의 총 건설시간을 출력한다.

 

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

 

2-0) MyIO

    // Inner Class - io process class
    private static class MYIO{
        // Variable
        BufferedReader br;
        StringTokenizer st;
        // Constructor
        public MYIO() {br=new BufferedReader(new InputStreamReader(System.in));}
        // Functions
        public void readLine() throws IOException {st=new StringTokenizer(br.readLine());}
        public int oneInt() throws IOException {return Integer.parseInt(br.readLine());}
        public int nextInt() {return Integer.parseInt(st.nextToken());}
    }

MyIO는 중복되어 많이 사용되는 BufferedReader와 StringTokenizer를 짧게 작성하여 사용하고자 만든 클래스입니다!

 

2-1) Input

    public static void main(String[] args) throws IOException{
        // Input
        MYIO io = new MYIO();
        int n = io.oneInt();
        
        // initialize
        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++){
            // save construction delay time
            io.readLine();
            int val = io.nextInt();
            delayArr[i] = val;
            // make connection between need and i (connection direction : need -> i)
            int need;
            while((need=io.nextInt())!=-1){
                if(outdeg[need]==null) outdeg[need]=new ArrayList<>();
                outdeg[need].add(i);
                indeg[i]++;
            }
        }
    }

 

 

2-2) Logic & Output

    public static void main(String[] args) throws IOException{
        // Logic
        // find zero indegree
        int[] timeArr = new int[n+1]; // 각 건물까지의 총 소요시간(3을 짓기위해 1의 건축이 필요하다면 1+3이 저장되는 구소)
        Queue<Integer> q= new ArrayDeque<>(); // 위상정렬을 위한 큐
        for(int i=1;i<=n;i++){
            // if indegree equals zero add it into q and set total construction time eqals construction delay time 
            if(indeg[i]==0){
                q.add(i);
                timeArr[i] = delayArr[i];
            }
        }
        // topological sort
        while(!q.isEmpty()){
            // get a current number from q
            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
                timeArr[next]=Math.max(timeArr[next],timeArr[cur]+delayArr[next]);
                // subtract indegree value and add it into q if indegree eqals zero 
                if(--indeg[next]==0) q.add(next);
            }
        }
        // Output
        for(int i=1;i<=n;i++) System.out.println(timeArr[i]);
    }

 

3) 전체코드

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

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

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

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