[알고리즘풀이]백준 2623 : 음악프로그램 JAVA

목차

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

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 2623번 음악프로그램을 풀었습니다. 이를 정리해보고자 합니다.

2623번: 음악프로그램

 

본문

1) 문제

 

2) 과정

이 문제를 먼저 풀었다가 2252를 풀고 돌아와서 다시 풀어보았던 문제였습니다.

[알고리즘풀이]백준 2252 : 줄 세우기 JAVA

 

하지만 그럼에도 사이클 체크하는 과정이 오래걸려서 총 5시간 정도 걸려 풀었습니다. 이 문제는 사이클의 유무를 체크하는게 가장 중요한 포인트였다 생각합니다.. 저의 삽질로그 이번 문제는 쫌 기니까 깃헙 방문하셔서 한번 확인해주세요... 아마 해당 문제를 풀고 계신 분들껜 어떤게 문제였는지 감이 오실만큼 잘 기록해뒀습니다...!!!

 

(2252는 사이클 체크할 필요가 없었어요 ㅠㅠㅠ)

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

1. 입력 - 진입간선의 수, 진출간선의 정보를 저장한다.
2. 로직 - 입력간선의 수가 0인 노드를 찾아 큐에 넣어준다(= 시작점 셋팅)
          - 위상정렬을 실시한다.
3. 출력할 값들의 수가 n과 같다면(사이클이 없다면) 정렬 결과를 출력하고, 아니라면 0을 출력한다.

 

 

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

 

2-0) MyReader

    // Inner Class - Read Input values
    private static class MyReader{
        BufferedReader br;
        StringTokenizer st;
        public MyReader(){ br = new BufferedReader(new InputStreamReader(System.in));}
        public void readLine() throws IOException{ st = new StringTokenizer(br.readLine());}
        public int nextInt(){ return Integer.parseInt(st.nextToken());}
    }

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

 

2-1) Input

    private static ArrayList<Integer>[] extArr;
    private static int[] entArr;
    private static boolean[] visited, innerVisited;

    public static void main(String[] args) throws IOException{
        // Input
        MyReader mr = new MyReader();
        mr.readLine();
        int n = mr.nextInt(); // 노드의 수 
        int m = mr.nextInt(); // 보조피디의 수

        // initialize
        entArr = new int[n+1]; // 각 노드의 진입차수를 저장하기 위한 배열
        extArr = new ArrayList[n+1]; // 각 노드의 진출간선들을 담기 위한 배열
        for(int i=1;i<=n;i++) extArr[i] = new ArrayList<>(); // extArr에 값들을 바로바로 넣을 수 있게 ArrayList를 new해둠
	}

 

 

2-2) Logic

    public static void main(String[] args) throws IOException{
        // Logic
        // make connection
        for(int i=0;i<m;i++){
            // read a line
            mr.readLine();
            int cnt = mr.nextInt();
            // 입력 cnt가 0일 경우를 판단함.
            if(cnt==0) continue;
            int tmp = mr.nextInt();
            // connecting
            for(int loop=1;loop<cnt;loop++){
                int one = mr.nextInt();
                // tmp와 one의 간선이 없다면, 둘을 연결하고 one의 진입차수를 1증가시킨다.
                extArr[tmp].add(one);
                entArr[one]++;
                tmp = one;
            }
        }
        // initialize
        Queue<Integer> q = new ArrayDeque<>();
        ArrayList<Integer> ansList = new ArrayList<>();
        // find indegree euqals zero 
        for(int i=1;i<=n;i++) if(entArr[i]==0) q.add(i); 
        // do topological sort
        while(!q.isEmpty()){
            // get a number
            int cur = q.poll();
            ansList.add(cur);
            // do preorder traversal
            for(int next:extArr[cur]) {
                // cut the edge -> subtract the degree of entry
                entArr[next]--;
                // if indegree  is 0, put it in the q
                if(entArr[next]==0) q.add(next);
            }
        }
    }

 

2-3) Output

        // Output
        if(ansList.size()!=n) System.out.println(0);
        else {
            StringBuilder sb = new StringBuilder();
            for(int cur : ansList) sb.append(cur+"\n");
            System.out.print(sb.toString());
        }

 

3) 전체코드

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

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

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

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