[알고리즘풀이]백준 2637 : 장난감 조립 JAVA

목차

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

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 2637번 장난감 조립을 풀었습니다. 이를 정리해보고자 합니다.

2637번: 장난감 조립

 

본문

1) 문제

2) 과정

항상 위상정렬을 풀때마다 indegree를 세는 방식이었어서 머리로는 진출차수를 세야함을 알았음에도 indegree를 세는 방식을 고집하다가 6시간이나 걸려 풀었던 문제입니다.

메모리초과도 초반에 만나서 변수도 정리해보고 TreeMap대신 LinkedHashMap도 사용해 봤지만 소용이 없어 아예 갈아엎고 코드를 다시 짰습니다. 물론 통과하고도 개선한다고 코드 정리를 했구요!! 별거 없지만 그 과정이 궁금하시다면 전체 코드에 게재된 링크를 확인해주세요 :)

 

제가 생각한 이번 문제의 핵심은 다른 topological sort와 달리 outdegree를 세고 진입하는 노선들을 arrayList로 담는 거라 생각했고, 이를 위해 사용했던 아이디어는 다음과 같습니다.

1. leaf에서 root로 타고올라가는 문제이지만 기본부품(=root)을 찾아야하기 때문에 탐색 전에 basic에 이들을 담아준다.
2. 큐(q)와 필요한 부품의 수를 구하는 배열(needArr)에 최종부품인 n의 번호와 갯수를 담아준다.
3. 큐가 빌때까지 needArr에 값을 갱신하며 이전노드의 진출차수를 끊어간다.
4. 큐를 다 돌았다면 기본부품들의 needArr값(needArr[basic의 요소들])을 가져와 출력한다.

 

2-0) MyIO

    // Inner Class - Read & Write values
    private static class MyIO{
        // Variable
        BufferedReader br;
        StringTokenizer st;
        // Constuctor
        public MyIO(){ br = new BufferedReader(new InputStreamReader(System.in));}
        // Method - for input
        public void readLine() throws IOException { st = new StringTokenizer(br.readLine());}
        public int nextInt(){ return Integer.parseInt(st.nextToken());}
    }

BufferedReader로 읽어온 값은 StringTokenizer로 잘라 가져오는 과정이 많이 중복되어 사용되어 이를 통합하여 값을 제공해주는 MyIO라는 클래스를 만들어 사용했습니다.

 

2-1) Input

    public static void main(String[] args) throws IOException {
        // Input
        MyIO io = new MyIO();
        io.readLine();
        int n = io.nextInt(); // 총 노드의 수이자 완제품의 번호
        // initialize
        int[] outdeg = new int [n+1];
        ArrayList<int[]>[] indeg = new ArrayList[n+1];
        // make connection
        io.readLine();
        for(int m=io.nextInt();m>0;m--){
            io.readLine();
            // y->x
            int x = io.nextInt();
            int y = io.nextInt();
            int k = io.nextInt();
            // make connections and count out-degree 
            if(indeg[x]==null) indeg[x]=new ArrayList<>();
            indeg[x].add(new int[]{y,k});
            outdeg[y]++;
        }

        // find indegree zero (find 기본부품) (내 코드는 진입노드가 없는 경우 배열값에 arrayList를 new하지 않음)
        ArrayList<Integer> basic = new ArrayList<>(); // 기본부품들을 담아둘 리스트
        for(int i=1;i<=n;i++) if(indeg[i]==null) basic.add(i); 
	}

 

 

2-2) Logic & Output

    public static void main(String[] args) throws IOException {
        // Logic
        // initialize for searching
        Queue<Integer> q= new ArrayDeque<>(); // leaf노드부터 탐색을 위해 사용할 큐
        q.add(n);   // 제작의 가장 마지막인 부품번호 n을 넣어줌
        int[] needArr = new int[n+1];
        needArr[n] = 1;
        // do topological sort
        while(!q.isEmpty()){
            // get a number
            int cur = q.poll();
            // check if cur is root node
            if(indeg[cur]==null) continue;
            // for the next
            for(int[] prev : indeg[cur]){
                int num = prev[0];
                int cnt = prev[1];
                // needArr에 기존(cur)에서 요구하는 개수와 새로운 개수를 곱해서 담아줌.
                needArr[num] += (needArr[cur]*cnt);
                // outdegree가 더이상 없으면 타고 올라가야하기 때문에 q에 추가
                if(--outdeg[num]==0) q.add(num);
            }
        }
        // Output
        for(int bNum : basic) System.out.println(bNum+" "+needArr[bNum]);
    }

 

 

3) 전체코드

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

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

https://github.com/Park1122/Algorithm-Study/blob/master/sujeong/topological_sort/BOJ2637.java#L52

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