백준 : 2252 DFS ,BFS

줄세이구 풀이방버은 DFS 접근과 BFS 접근이 있다.

 

1. DFS 풀이방법

 

보기에서 주어지는 순서는 그래프를 나타낸다 필드상에 여러그래프들을 DFS 탐색하고 종료되는 순서 stack에 저장한다.

Stack 에 pop하는 순서대로 위상정렬된 순서이다.

 

2. BFS 풀이방법.

 

u->v 로간다면 v의 카운터를 1증가시킨다. 이렇게보면 현재 줄을 세울수 있는 사람은 cnt = 0인 사람이다.

 

이원리로 BFS탐색을한다면 위상정렬이 이루어 진다.

 

DFS 코드

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class 줄세우기DFS {
	static int N, M;
	static ArrayList<Integer> ver[];
	static Stack<Integer> stack = new Stack<Integer>();
	static boolean visit[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str;

		str = br.readLine().split(" ");

		N = Integer.parseInt(str[0]);
		M = Integer.parseInt(str[1]);
		visit = new boolean[N + 1];
		ver = new ArrayList[N + 1];

		for (int n = 1; n <= N; n++) {
			ver[n] = new ArrayList<Integer>();
		}

		for (int i = 0; i < M; i++) {
			str = br.readLine().split(" ");
			int u = Integer.parseInt(str[0]);
			int v = Integer.parseInt(str[1]);

			ver[u].add(v);
		}

		for (int n = 1; n <= N; n++) {
			if(visit[n])
				continue;
			dfs(n);
		}
		
		StringBuilder sb = new StringBuilder();
		while(!stack.isEmpty()) {
			sb.append(stack.pop()).append(' ');
		}
		System.out.println(sb.toString());
	}

	public static void dfs(int n) {
		
		visit[n] = true;
		for(int next : ver[n]) {
			if(visit[next])
				continue;
			dfs(next);
		}
		stack.add(n);
		
	}
}

BFS 코드

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class 줄세우기BFS {
	static int N, M;
	static int Cnt[];
	static ArrayList<Integer>[] list;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str;

		str = br.readLine().split(" ");

		N = Integer.parseInt(str[0]);
		M = Integer.parseInt(str[1]);
		list = new ArrayList[N + 1];
		Cnt = new int[N + 1];

		for (int n = 1; n <= N; n++) {
			list[n] = new ArrayList<Integer>();
		}
		
		for (int i = 0; i < M; i++) {
			str = br.readLine().split(" ");
			int u = Integer.parseInt(str[0]);
			int v = Integer.parseInt(str[1]);
			list[u].add(v);
			Cnt[v]++;
		}
		
//		PriorityQueue<Pair> q = new PriorityQueue<>();
		Queue<Integer> q = new LinkedList<Integer>();
		for (int n = 1; n <= N; n++) {
			if (Cnt[n] == 0) {
				q.add(n);
			}
		}
		StringBuilder ans = new StringBuilder();
		while (!q.isEmpty()) {
			int cur = q.poll();
			ans.append(cur).append(' ');

			for (int next : list[cur]) {
				if (Cnt[next] == 0)
					continue;
				Cnt[next]--;
				if (Cnt[next] == 0) {
					q.add(next);
				}
			}
		}
		System.out.println(ans.toString());
	}

	static StringBuilder sb = new StringBuilder();
}