[SWEA D6] 작업순서 - JAVA

문제 링크

문제 정의

• $V$개의 작업과 $E$개의 작업 순서가 주어짐
• 선행 순서에 따라 가능한 작업 순서들 중 하나를 출력

---

접근 방법

이 문제는 기본적인 위상 정렬 문제입니다.
위상 정렬 문제를 안 푼지 오래 되었기 때문에 차례대로 코드를 작성하면서 기억을 떠올렸습니다.

초기화

우선 위상정렬에 필요한 것은 인접 리스트입니다.
메모리 공간의 효율을 위해 필드를 최소화한 커스텀 연결 리스트를 사용했습니다.

커스텀 연결 리스트

class Edge {
	int v;
    Edge edge;
    public Edge (int v, Edge edge) {
    	this.v = v;
        this.edge = edge;
    }
}

초기화

// static 선언
static Edge[] graph;

// 초기화
graph = new Edge[V+1];

그 다음으로 필요한 것은 진입 차수 배열입니다.
진입 차수 배열의 특정 인덱스는 해당 정점이 선행으로 작업해야할 작업이 몇개 남았는지를 확인합니다.

// static 선언
static int[] in; 

// init() 메서드 내부에서 초기화
in = new int[V+1]

그 다음은 간선들의 입력을 받는 부분에서 눈여겨 봐야할 부분은 진입 차수 증가입니다.
$u$가 $v$의 선행 작업이므로
$v$는 $u$라는 선행 작업을 완료해야 작업을 진행할 수 있습니다.
그렇기 떄문에 진입 차수는 $v$를 증가시켜 줍니다.

in[v]++;

---

핵심 로직

다음은 위상 정렬의 핵심 로직입니다.
우선 진입 차수가 0이여서 선행할 작업이 없는 작업들부터 파악해서 큐에 저장합니다.

for (int v = 1; v <= V; v++) {
	if (in[v] == 0) {
		q.offer(v);
	}
}

그 다음 해당 작업을 완료하면서
해당 작업이 필요한 작업들 nv의 진입 차수들을 1씩 내려줍니다.
이 때 v작업을 완료함으로써 선행 작업이 없어진 nv들을 큐에 저장합니다.

for (Edge edge = graph[v]; edge != null; edge = edge.edge) {
	int nv = edge.v;
	if (--in[nv] == 0) q.offer(nv);
}

이 로직을 반복하면서 모든 작업들을 완료할 때까지 진행하며
루프의 끝 부분에서 끝난 작업들을 StringBuilder에 저장한 후
출력하게 되면 문제를 해결할 수 있습니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

class Edge {
    int v;
    Edge edge;

    public Edge (int v, Edge edge) {
        this.v = v;
        this.edge = edge;
    }
}


public class Solution {
    static final int T = 10;
    static StringTokenizer st;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int V;
    static int E;
    static Edge[] graph;
    static int[] in;
    public static void main(String[] args) throws IOException {

        StringBuilder sb = new StringBuilder();
        for (int t = 1; t <= T; t++) {
            init();
            sb.append("#").append(t).append(" ").append(TopologicalSort()).append("\n");
        }
        System.out.print(sb);
    }

    static String TopologicalSort() {
        ArrayDeque<Integer> q = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();

        for (int v = 1; v <= V; v++) {
            if (in[v] == 0) {
                q.offer(v);
            }
        }

        while (!q.isEmpty()) {
            int v = q.poll();
            for (Edge edge = graph[v]; edge != null; edge = edge.edge) {
                int nv = edge.v;
                if (--in[nv] == 0) q.offer(nv);
            }

            sb.append(v).append(" ");
        }

        return sb.toString();
    }

    static void init() throws IOException {
        st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        graph = new Edge[V+1];
        in = new int[V+1];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < E; i++) {
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            graph[u] = new Edge(v, graph[u]);
            in[v]++;
        }
    }
}