[백준 2252] 줄 세우기 (C++, JAVA)

문제 링크: https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

1. 주의할 점

- 위상정렬을 사용할 줄 알아야 한다

 

2. 구현

- 선행되는 A의 Node에 후행되는 Node B를 추가한다. 그리고 Conn[B]++를 통해 B의 앞에 선행되는 Node가 증가되었음을 표시한다

- For문을 통해 Node 1~N까지 돌며 Conn[]의 값이 0이면 큐에 넣는다

- 큐에서 원소를 뽑으면서 해당 원소를 출력하고, 해당 원소의 후행 Node가 있는 경우, 후행Node의 Conn[] 값을 1 줄인다. 1을 줄인후, Conn[]의 값이 0 되었다면 큐에 넣는다

 

[C++]

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> v[32001];
int connection[32001];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int num, edge, start, end;
	cin >> num >> edge;
	for (int i = 0; i < edge; i++) {
		cin >> start >> end;
		v[start].push_back(end);
		connection[end]++;
	}
	queue<int> q;
	for (int i = 1; i <= num; i++)
		if (connection[i] == 0)
			q.push(i);
	for(int i=0;i<num;i++){
		int cidx = q.front();
		q.pop();
		cout << cidx << " ";
		for (int j = 0; j < v[cidx].size(); j++) {
			connection[v[cidx][j]]--;
			if (connection[v[cidx][j]] == 0)
				q.push(v[cidx][j]);
		}
	}
	system("pause");
	return 0;
}

 

[JAVA]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_bj_2252_줄세우기 {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s);
		int node = Integer.parseInt(st.nextToken());
		int edge = Integer.parseInt(st.nextToken());
		List<Integer> li[] = new List[node+1];
		int conn[] = new int[node+1];
		for(int i=1;i<=node;i++)
			li[i] = new ArrayList<Integer>();
		
		for(int i=0;i<edge;i++) {
			s = br.readLine();
			st = new StringTokenizer(s);
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			li[start].add(end);
			conn[end]++;
		}
		Queue<Integer> q = new LinkedList<Integer>();
		for(int i=1;i<=node;i++) {
			if(conn[i]==0) {
				q.offer(i);
			}
		}
		while(!q.isEmpty()) {
			int cidx= q.poll();
			System.out.print(cidx+" ");
			for(int i=0;i<li[cidx].size();i++) {
				int next = li[cidx].get(i);
				conn[next]--;
				if(conn[next]==0) {
					q.offer(next);
				}
			}
		}
	}
}