[ 백준 ] 2252 줄 세우기

Link | 백준 2252번 문제 : 줄 세우기

📌 About

학생을 node으로 표현할 때 더 작은 학생이 더 큰 학생을 가리키는 graph가 있다.

Node가 탐색되기 위해서는 이전 node를 우선 탐색해야 한다.

이 때 사용할 수 있는 알고리즘이 위상 정렬이다.

위상 정렬에 대한 간단한 내용과 코드는 다음을 참고하면 된다.

Topological Sorting

📌 Solution

진입차수 리스트와 포인팅 nodes map을 초기화한다.

List<Integer> degrees = new ArrayList<>();				// 진입차수를 저장한다.
Map<Integer, List<Integer>> next = new HashMap<>();		// 가리키는 node들을 저장한다.

// 주어진 Node 크기에 맞게 초기화한다.
for (int nno = 1; nno <= N; nno++) {
    degrees.add(0);
    next.put(nno, new ArrayList<>());
}

주어진 edge 정보를 바탕으로 값을 저장한다.

while (M-- > 0) {
    tokenizer = new StringTokenizer(reader.readLine());
    int smaller = Integer.parseInt(tokenizer.nextToken());	// 작은 키의 학생
    int bigger = Integer.parseInt(tokenizer.nextToken());	// 큰 키의 학생
    degrees.set(bigger - 1, degrees.get(bigger - 1) + 1);	// 진입차수 가산
    next.get(smaller).add(bigger);							// 가리키는 node 추가
}

위상을 정렬한다.

// 진입차수가 0인 node들을 저장하는 queue로 다음으로 탐색한 node를 poll 할 수 있다.
Queue<Integer> readies = IntStream.rangeClosed(1, N).boxed()
        .filter(n -> degrees.get(n - 1) == 0)
        .collect(Collectors.toCollection(LinkedList::new));
        
// Queue를 poll하면서 node를 탐색한다
while (!readies.isEmpty()) {
	// 탐색할 node가 가리키는 node들의 진입차수를 감산하고 0이 되면 queue에 추가한다.
    for (int nno : next.get(readies.peek()))
        if (degrees.set(nno - 1, degrees.get(nno - 1) - 1) == 1) readies.offer(nno);
    
    // 탐색한 node를 출력한다. (출력한 순서가 정렬된 순서)
    result.append(readies.poll()).append(" ");
}

📌 Code

GitHub Repository

public void solve() throws IOException {
    StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
    int N = Integer.parseInt(tokenizer.nextToken());
    int M = Integer.parseInt(tokenizer.nextToken());

    List<Integer> degrees = new ArrayList<>();
    Map<Integer, List<Integer>> next = new HashMap<>();

    for (int nno = 1; nno <= N; nno++) {
        degrees.add(0);
        next.put(nno, new ArrayList<>());
    }

    while (M-- > 0) {
        tokenizer = new StringTokenizer(reader.readLine());
        int smaller = Integer.parseInt(tokenizer.nextToken());
        int bigger = Integer.parseInt(tokenizer.nextToken());
        degrees.set(bigger - 1, degrees.get(bigger - 1) + 1);
        next.get(smaller).add(bigger);
    }

    Queue<Integer> readies = IntStream.rangeClosed(1, N).boxed()
            .filter(n -> degrees.get(n - 1) == 0).collect(Collectors.toCollection(LinkedList::new));
    while (!readies.isEmpty()) {
        for (int nno : next.get(readies.peek()))
            if (degrees.set(nno - 1, degrees.get(nno - 1) - 1) == 1) readies.offer(nno);
        result.append(readies.poll()).append(" ");
    }
}