백준 2252 자바 - 줄 세우기 (BOJ 2252 JAVA)

문제 : boj2252

 

 

1. 그래프로 생각해보자.

  이런식으로 A에서 B로 향한다던지, A와 B가 연관되었다든지 하면 일단 그래프로 생각해보는게 이해하기 편하다. 이 문제에서는 'A가 학생 B의 앞에 서야 한다'에 대해 A에서 B로의 간선을 긋는 방향 그래프로 생각해보자.

 

  그럼 다음과 같은 경우를 보자.

5 3
1 2
2 3
4 5

위의 경우를 그래프로 나타내보면 다음과 같다.

위와 같은 경우는 간단하다. 이 문제의 경우 1->2->3을 먼저 가던지, 4->5를 먼저 가던지, 심지어 1->4->2->3->5 이렇게 가던지 상관없다. 서로 섞여있더라도 아무튼 모든 경우에서 A가 B보다 먼저 나오기만 하면 된다.

 

그렇다면 M개의 A, B를 입력받으면서, A에 나타났으면서 B에는 등장하지 않은 1과 4어디에서든 BFS나 DFS를 돌리면 될 거라고 생각할 수 있다.

 

 

그럼 이번엔 다른 경우를 그래프로 그려본 다음을 봐보자.

마찬가지로 A에 등장했지만 B에는 등장하지 않은 1과 5부터 단순히 BFS나 DFS를 돌리면 오답이 되게 된다.

1->2->3->5->4 를 하게 되면 4->2가 만족되지 않는다.

5->4->2->3->1 도 마찬가지로 1->2가 만족되지 않는다.

 

 

2. 간선의 개수를 세서 해결해보자.

2.1

  결국 위와 같은 문제가 생기는 경우는, 현재 자신을 향하는 간선이 1개 초과일 때 발생한다. 그러니 이번엔 다음과 각 정점에서 자기 자신으로 들어오는 간선의 개수를 세보자. 이후 자기자신으로 들어오는 간선의 개수를 '차수'라고 하겠다.

 

2.2

  이렇게 하면 해결할 방법이 좀 더 보인다. '1'때와 마찬가지로 A에서 등장했지만 B엔 등장하지 않은 곳들은 모두 차수가 0일 것이다. 따라서 차수가 0인 곳 중 아무곳에서나 시작한다. 1번 정점에서 시작해보자. 1번정점을 들리고 2번 정점을 들렸다. 여기까지 '1->2'가 된다. 그리고 차수가 2이상인 곳을 만났으므로 더 진행하지 않고, 다른 간선을 역방향으로 끝까지 따라가서 5번 정점에서 다시 진행한다. 물론 이 예시와 달리 따라가는 중간에 다른 차수가 2 이상인곳을 만난다면 위의 과정을 재귀적으로 수행하면 될 것이다.

 

2.3

  그럼 5번정점에서 5->4->2로 다시 차수가 2이상이었던 곳으로 돌아왔고, 마지막으로 3번 정점을 향하면 될 것이다. 최종적으로 '1->2->5->4->3'이 될 것이다.

 

 

 

 

3. 더 간단한 방법이 없을까?

  '2'의 과정을 통해서도 별다른 반례가 생각나지 않으므로 일단 가능하다고 생각이 든다(제 생각임). 하지만 간선을 역으로 타고 들어가기 위해 추가 메모리(역방향 간선 유지)와 추가 시간이 들어갈 것이다. 그리고 로직도 더 복잡하다!

 

  이걸 해결하기 위한 더 간단한 방법이 있다. 애초에 이 문제에서는 아무튼 M개의 A->B 순서만 전부 맞다면 간선을 DFS 형태로 깊이 있게 진행하지 않아도 상관이 없다. 무슨말이냐면 '5->1->4->2->3'과 같이 마구 왔다갔다 거리면서 진행해도 아무튼 A->B 순서만 전부 맞으면 상관이 없다는 얘기이다.

 

  그러니 마치 BFS를 진행하듯이 큐를 이용해 진행할 건데(DFS처럼 스택이나 재귀로 해도 상관없다), 우선 처음에 차수가 0인 부분을 전부 큐에 넣어준다. 그리고 아무거나 빼내고(아무거나 빼도 되므로 큐, 스택, 재귀 모두 상관없다.), 해당 정점에서 갈 수 있는 모든 간선을 확인하면서 도달한 정점의 차수를 1 빼준다. 그러다가 차수가 0이 되는 경우 해당 정점도 큐에 넣어준다. 이걸 계속 반복해 나가면서 출력만 해주면 된다!

 

  이와 같은 과정을 '위상 정렬(topological sorting)' 이라고 부른다. 어떠한 방향 그래프에서 정점 방문 순서를 거스르지 않으면서 모든 정점을 한 줄로 모두 나열하기 위한 알고리즘이다.

 

  '2'와 같은 예시에 대해 이 과정을 한번 봐보자.

3.1 

 우선 큐에 처음부터 차수가 0인 정점을 넣어준다. 1, 5가 들어갈 것이다. 대충 아무거나 방문해도 상관없지만 아무튼 큐 이므로 좌측에서 넣어다치고 우측꺼부터 방문해보자.

 

3.2

  정점 5를 큐에서 꺼내서 방문했고, 5를 출력해준다. 그리고 간선을 통해 진행 가능한 정점 4의 차수를 1 빼준다. 차수가 0이 되었으므로 정점 4도 큐에 넣어준다.

 

3.3

  이번엔 큐에서 꺼낸 정점1을 방문한다. 마찬가지로 정점 2의 차수를 1 빼준다. 아직 차수가 남아있으므로 어딘가에서 정점 2를 방문 해야 모든 A->B를 만족시킬 수 있다. 그러니 정점 2는 큐에 추가되지 않는다.

 

3.4

  큐에 있던 정점 4를 방문했고, 갈 수 있는 정점 2의 차수를 1 빼준다. 정점 2도 차수가 0이 되었으므로 큐에 추가한다.

 

 

3.5

  큐에 있던 정점 2를 방문했고, 마찬가지로 정점 3의 차수를 1 빼주고 0이 되었으므로 큐에 추가해준다.

 

 

3.6

  마지막 정점 3을 방문했고, 큐가 비었으므로 더이상 진행할 수 없으니 끝났다!

 

 

4. 모든 경우에 적용 가능할까?

  그렇진 않다. 사이클이 있는 방향 그래프에서는 적용이 되지 않는다. 간단히 말해서 모든 정점을 방문하지 않았는데 이미 큐가 비었다면 사이클이 있었다는 얘기이고, 이 경우 위상 정렬이 불가능하다. 다만 이 문제에서는 '일부 학생들의 키를 비교한 결과'가 주어졌는데 사이클이 생긴다면, 애초에 키를 잘못 쟀다는 얘기이고 애초에 문제 자체가 틀린게 된다. 실제로도 별도로 처리해주지 않아도 통과 된다.

 

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;

public class Main extends FastInput {
    private static void solution() throws Exception {
        int n = nextInt();
        int m = nextInt();
        ArrayList<Integer>[] edges = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();
        int[] cnt = new int[n+1];

        while (m-->0) {
            int a = nextInt();
            int b = nextInt();
            cnt[b]++;
            edges[a].add(b);
        }

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            if (cnt[i] == 0)
                q.add(i);
        }

        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            int cur = q.poll();
            sb.append(cur).append(' ');
            for (int next : edges[cur]) {
                if (--cnt[next] == 0)
                    q.add(next);
            }
        }

        System.out.println(sb);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}