백준 2623 음악프로그램(위상정렬, DFS, BFS)

2623번: 음악프로그램

재미있는 문제였다. 각 PD들이 가수들의 무대순서를 정하고 각각 PD에 요청에 모두 부합하는 완벽한 순서를 만들어내는 것이 문제다.

 

먼저 문제를 읽고 생각을 해봤을 때 순서라는 점이 가장 Key-Point라는 생각이 들었다.

따라서 순서라는 점을 계속 기억하고 인지하기 위해 Queue, Stack이라는 자료구조를 통해서 기억했으면 좋겠다라는 생각을 했고 더 나아가서 이 자료구조를 통해서 Next step까지 생각하는거니까 DFS, BFS문제구나! 라고 최종적으로 생각했고 찾아보니까 내가 한 생각이 위상정렬이라는 알고리즘과 동일하다

 

위상정렬이라는 알고리즘을 자세하게 알진 못했지만 내가 한 생각이 그대로 이 문제의 실마리가 되었다는게 뿌듯한 문제였다.

 

BFS(Queue)

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

public class Main {
	static int n,m;
	static List<Integer>[] board;
	static List<Integer> res;
	static int[] data;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
	
		board = new ArrayList[n+1];
		for (int i = 1; i <n+1; i++) {
			board[i] = new ArrayList<>();
		}
		
		data = new int[n+1];
		res = new ArrayList<>();
		for (int i = 0; i < m; i++) {
			String[] input = br.readLine().split(" ");
			
			for (int j = 1; j < Integer.parseInt(input[0]); j++) {
				int from = Integer.parseInt(input[j]);
				int to = Integer.parseInt(input[j+1]);
				board[from].add(to);
				data[to]++;
				}
		}

		bfs();
		
		if(res.size() == n) {
			for(Integer num:res)
				System.out.println(num);
		}
		else
			System.out.println(0);
	}
	
	
	public static void bfs() {
		Queue<Integer> queue = new ArrayDeque<>();
		for (int i = 1; i < n+1; i++) {
			if(data[i]==0)
				queue.add(i);
		}
		
		
		while(!queue.isEmpty()) {
			int v = queue.poll();
			res.add(v);
			
			for(Integer num:board[v]) {
				data[num]--;
				
				if(data[num]==0)
					queue.add(num);
			}
		}
		return;
		
		
	}

}

 

DFS(Stack) - 틀린 코드인데 왜 틀렸는지 모르겠음 ㅠ

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

public class Main{
	static int n,m;
	static List<Integer>[] board;
	static Stack<Integer> stack;
	static boolean[] visited;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
	
		board = new ArrayList[n+1];
		for (int i = 1; i <n+1; i++) {
			board[i] = new ArrayList<>();
		}
		
		visited = new boolean[n+1];
		stack = new Stack<>();
		for (int i = 0; i < m; i++) {
			String[] input = br.readLine().split(" ");
			
			for (int j = 1; j < Integer.parseInt(input[0]); j++) {
				int from = Integer.parseInt(input[j]);
				int to = Integer.parseInt(input[j+1]);
				board[from].add(to);
				}
		}

		topologySort(0);
		
		if(stack.size() == n) {
			for (int i = 0; i < n; i++) {
				System.out.println(stack.pop());
			}
		}
		else
			System.out.println(0);
	}
	
	public static void topologySort(int depth) {
        for(int i = 1; i < n+1; i++) {
            if(!visited[i]){
                dfs(i);
            }
        }
	}
	
	
	

	public static void dfs(int depth) {
        visited[depth] = true;

        for(int v : board[depth]){
            if(!visited[v]){
                dfs(v);
            }
        }
        stack.add(depth);
    }

}