BOJ - 줄 세우기

2252 줄 세우기 : https://www.acmicpc.net/problem/2252

---

Problem

---

Solve

A와 B가 주어진다면 A가 B보다 앞에서야 합니다. B에 대해 먼저 나와야하는 순서가 있고 답이 여러가지인 경우 아무거나 출력해도 되기때문에 위상정렬을 생각하였습니다.

1차원 배열을 이용해 indegree를 초기화하였고 indegree[i]가 0인 경우 자신보다 앞서야 하는 것이 없기 때문에 해당 값을 저장하는 과정을 구현했습니다.

	static Queue<Integer> topologicSort(int[] indegree, List<Integer>[] edges) {
    	//키순으로 세워놓은 값 저장
		Queue<Integer> result = new LinkedList<>();
        //indegree가 0인 즉, 앞에 서야하는 인원이 없거나 이미 서야하는 인원이 서있는 값 저장
		Queue<Integer> queue = new LinkedList<>();

		//초기에 앞에 서야하는 값을 찾아 queue에 저장해줍니다.
		for (int i = 1; i < indegree.length; i++) {
			if (indegree[i] == 0) {
				queue.offer(i);
			}
		}

		while (!queue.isEmpty()) {
			int current = queue.poll();
            //해당 값을 줄에 세워줍니다.
			result.offer(current);

			/*
            해당 값보다 뒤에 위치해야하는 값들의 indegree를 감소시켜주며
            연결되어있는 값이 0이 되는 경우 queue에 넣어서 줄을 세우고 비교한 인원들을 찾아주도록 합니다.
            */
			for (int edge : edges[current]) {
				indegree[edge]--;

				if (indegree[edge] == 0) {
					queue.offer(edge);
				}
			}
		}

		return result;
	}

---

Code

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		int[] indegree = new int[N + 1];
		List<Integer>[] edges = new List[N + 1];
		for (int i = 0; i <= N; i++) {
			edges[i] = new ArrayList<>();
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int front = Integer.parseInt(st.nextToken());
			int back = Integer.parseInt(st.nextToken());

			indegree[back]++;
			edges[front].add(back);
		}

		Queue<Integer> result = topologicSort(indegree, edges);
		StringBuilder sb = new StringBuilder();
		while (!result.isEmpty()) {
			sb.append(result.poll()).append(" ");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	static Queue<Integer> topologicSort(int[] indegree, List<Integer>[] edges) {
		Queue<Integer> result = new LinkedList<>();
		Queue<Integer> queue = new LinkedList<>();

		for (int i = 1; i < indegree.length; i++) {
			if (indegree[i] == 0) {
				queue.offer(i);
			}
		}

		while (!queue.isEmpty()) {
			int current = queue.poll();
			result.offer(current);

			for (int edge : edges[current]) {
				indegree[edge]--;

				if (indegree[edge] == 0) {
					queue.offer(edge);
				}
			}
		}

		return result;
	}
}

---

Result

---

Reference