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

목차

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

 

 

개요

이번에 알고리즘 스터디에서 JAVA를 이용해 백준 2252번 줄 세우기를 풀었습니다. 이를 정리해보고자 합니다.

2252번: 줄 세우기

 

본문

1) 문제

 

2) 과정

처음 풀어본 위상정렬 문제여서 어렵다는 소문을 듣고 미리 공부를 좀 한뒤 풀었던 문제입니다.

간단하게 공부를 하면서 배운 내용으로 위상정렬을 정리하면 다음과 같습니다.

위상정렬
: 여러 가지 일들에 순서가 정해져 있을 때 순서에 맞게끔 나열하는 것.
- 순서가 있는 일을 순서에 맞게 나열하는 외출준비루틴, 선수과목에 따른 강의 신청 경우를 찾을 때 사용한다.
- 위상정렬의 조건은 사이클이 없어야 한다.(= 진입차수가 0인 정점이 있어야한다.)

 

4시간 정도를 걸려 문제를 풀었고 visited를 잘못사용하거나 entArr에서 값을 빼오는 방식을 잘못 사용해 "틀렸습니다" 결과를 받았었습니다.

 

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

1. 진입차수를 담는 배열과 진출 간선들을 담는 배열을 준비한다.
2. 연결 만들기 - 단순 for문으로만 조회할것이기 때문에 ArrayList사용하여 방향성있는 그래프를 표현함.
3. 진입차수가 0인 노드를 찾아 큐에 넣어줌 - 진입차수가 0이다 = 시작노드다 / 진입차수가 0인게 없다 -> 순환그래프라 위상정렬 불가
4. 큐에서 노드들을 빼내 출력한 뒤, 해당 노드와 연결된 노드들의 진입차수를 1 감소시키다 진입차수가 0인 노드가 되면 큐에 넣어 2~3의 탐색을 큐가 빌때까지 반복한다.
5. 정답을 출력한다.

 

설명은 주석! 자세한 내용은 깃헙링크!! 잊지말고 확인해주세요 😄

 

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

    // 들어오고 나가는게 여러개일 수 있으니 ArrayList로 사용
    private static ArrayList<Integer>[] extArr;
    private static int[] entArr;
    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 & Output

    public static void main(String[] args) throws IOException{
        // Logic
        // make connection
        for(int i=0;i<m;i++){
            // read a line
            mr.readLine();
            int one = mr.nextInt();
            int oth = mr.nextInt();
            // 방향성이 있는 그래프(one->oth)이기 때문에 one의 진출간선에 oth추가 및 oth의 진입차수 증가
            extArr[one].add(oth);
            entArr[oth]++;
        }
        // find indegree euqals zero 
        Queue<Integer> q = new LinkedList<>();
        for(int i=1;i<=n;i++){
            if(entArr[i]==0) q.add(i); 
        }
        // do topological sort
        StringBuilder sb = new StringBuilder();
        while(!q.isEmpty()){
            int cur = q.poll();
            // preorder traversal
            sb.append(cur+" ");
            for(int i:extArr[cur]) {
                // cut the edge -> subtract the degree of entry
                entArr[i]--;
                // if indegree  is 0, put it in the q
                if(entArr[i]==0) q.add(i);
            }
        }

        // Output
        System.out.println(sb.toString());
    }

 

 

3) 전체코드

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

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

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

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