2252번 - 줄세우기(bfs)

줄 세우기라는 골드 2티어 문제를 풀었다.

한번에 풀진 않았지만 어려운 문제는 아니였고, bfs를 사용하는 문제이다.

다음과 같은 입력값이 주어진다.

3 2
1 3
2 3

첫줄의 첫 숫자(N)는 학생이 몇 명인지, 두번째 숫자(M)는 몇개의 줄에 대한 정보가 주어질 것인지 나타낸다.

다음 M 개의 줄동안 입력이 주어지는데, 이는 학생의 위치를 의미한다.

즉 위의 보기에서는 1번 학생 뒤에 3번 학생, 2번 학생 뒤에 3번 학생이 온다는 의미이다.

 

처음에는 너무 복잡하게 생각한 나머지 틀리고 말았다.

누구 앞에 누가있는지, 누구 뒤에 누가 있는지 둘다 고려를 해버렸다.

결국 틀린 코드를 오래동안 작성했고, 아래는 틀린 보기이다.

public class 줄세우기_2252번_오답 {
    static int N, M;
    static ArrayList<Stack<Integer>> leftList;
    static ArrayList<Stack<Integer>> rightList;
    static boolean[] lined;
    static StringBuilder line;
    static int position = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        leftList = new ArrayList<>();
        rightList = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            leftList.add(new Stack<>());
            rightList.add(new Stack<>());
        }
        for (int i = 0; i < M; i++) {
            int A = sc.nextInt();
            int B = sc.nextInt();
            leftList.get(B).add(A);
            rightList.get(A).add(B);
        }
        lined = new boolean[N+1];
        line = new StringBuilder();

        int count = 0;
        for (int i = 1; i <= N; i++) {
            if (!lined[i]) {
                lineUp(count, i);
            }
        }
        System.out.println(line);

    }

    static void lineUp(int count, int student) {
        count++;
        line.insert(position, student + " ");
        lined[student] = true;

        while (!leftList.get(student).isEmpty()) {
            int temp = leftList.get(student).pop();
            if (!lined[temp]) {
                lineUp(count, temp);
            }
        }
        while (!rightList.get(student).isEmpty()) {
            position += count;
            count = 0;
            int temp = rightList.get(student).pop();
            if (!lined[temp]) {
                lineUp(count, temp);
            }
        }
    }
}

 

 

이후 조금의 휴식을 취한 뒤, 다시 생각해보았다.

'앞에 더이상 와야할 사람이 없다면, 그 즉시 줄세우면 된다' 라는 처음 생각한 대전재로 다시 돌아왔고,

줄세운 학생의 뒤에있는 학생들에게 한명의 학생이 줄을 섰다 라는걸 알리면 된다는 생각이 들었다.
그 결과 아래의 코드를 작성할 수 있었다.

import java.util.*;

public class 줄세우기_2252번 {
    static int N, M;
    static Queue<Integer> queue;
    static List<Integer>[] rightList;
    static int[] left;
    static StringBuilder sb;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        rightList = new ArrayList[N + 1];
        left = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            rightList[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            int A = sc.nextInt();
            int B = sc.nextInt();
            rightList[A].add(B);
            left[B]++;
        }

        queue = new LinkedList<>();
        sb = new StringBuilder();
        bfs();
        System.out.println(sb.toString());

    }

    static void bfs() {
        for (int i = 1; i <= N; i++) {
            if (left[i] == 0) {
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int temp = queue.poll();
            sb.append(temp + " ");
            for (int num : rightList[temp]) {
                left[num]--;
                if (left[num] == 0) {
                    queue.add(num);
                }
            }
        }
    }
}

 

과정을 설명하자면 아래와 같다.

1. 입력을 받을 때 어떤 학생 뒤에 와야하는 학생들을 list[]에 담아 놓는다.
   이때, 뒤에 와야하는 학생들에게는 앞에 몇명이 섰는지 남겨놔야 하니, left[]에 1씩 늘리며 저장한다.
2. 1~N까지 학생들을 점검하며, 자신에 앞에 아무도 서있을 필요가 없는 학생만 queue에 저장해 놓는다.
3. 큐에서 하나의 학생씩 뽑아내며 줄을 세운다.
   줄을 세웠다면, 해당 학생 뒤에 있는 학생(i)의 left[i]에 1을 빼준다. 앞에 와야하는 학생이 하나 줄기 때문이다.
4. 만약 left[i]에 1을 빼준 결과가 0이라면, queue에 추가해준다.
5. 3, 4번 과정을 반복한다. 그 결과 모든 학생들이 순서에 맞게 줄을 설 것이며, 큐가 비게 될것이다.