SWEA 1267_작업순서

위상정렬 쓰는 문제다. 

 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class SWEA_1267 { // Topological Sort via Q
	static int[][] board;
	static int[] enters; // 진입 수 
	static Queue<Integer> Q;
	
	public static void main(String[] args){
		 Scanner sc = new Scanner(System.in);
		
		for(int i = 0; i<10; i++) { // TC 10개
			int V = sc.nextInt(); // nodes
			int E = sc.nextInt(); // edges
			board = new int[V+1][V+1]; // V는 1부터 
			enters = new int[V+1];
			Q = new LinkedList<>();
			
			for(int j = 0; j<E; j++) {
				int A = sc.nextInt();
				int B = sc.nextInt();
				board[A][B] = 1;
				enters[B]++;
			}
			
			for(int j = 1; j<V+1; j++) {
				if(enters[j] == 0) Q.add(j); 
			}
			
			System.out.printf("#%d ", i+1);
			while(!Q.isEmpty()){
				int curr = Q.poll();
				System.out.printf("%d ", curr);
				for(int j = 0; j<V+1; j++) {
					if(board[curr][j] == 1) {
						enters[j]--;
						if(enters[j] == 0) Q.add(j);
					} // if
				} // for int j
			} // while
			
			System.out.println();
			
		}
	}
}

Q로 짤 때는 이렇게 하면 되고 

아래는 Stack을 쓰는 구조다. 

 

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;

public class SWEA_1267 { // Topological Sort via Stack
	static int[][] board;
	static int[] enters; // 진입 수
	static int V, E;
	// 스택으로 풀려면
	static Stack<Integer> stk;
	static boolean[] visited;
	
	public static void main(String[] args) throws FileNotFoundException {
		Scanner sc = new Scanner(new File("./input_1267.txt"));
		// Scanner sc = new Scanner(System.in);
		
		for(int i = 0; i<10; i++) { // TC 10개
			V = sc.nextInt(); // nodes
			E = sc.nextInt(); // edges
			board = new int[V+1][V+1]; // V는 1부터 
			enters = new int[V+1];
			stk = new Stack<>();
			visited = new boolean[V+1];
			
			for(int j = 0; j<E; j++) {
				int A = sc.nextInt();
				int B = sc.nextInt();
				board[A][B] = 1;
				enters[B]++;
			}
			
			for(int j = 1; j<V+1; j++) {
				if(enters[j] == 0) DFS(j);
			}
			
			System.out.printf("#%d ", i+1);
			while(!stk.isEmpty()){
				System.out.printf("%d ", stk.pop());
			} // while
			
			System.out.println();
		}
	}
	
	static void DFS(int j) {
		visited[j] = true;
		for(int i = 1; i<V+1; i++) {
			if(board[j][i] == 1) {
				DFS(i);
			}
		}
		
		stk.add(j);
	}
}

이렇게 하면 

왜 마지막 케이스는 나오지 않을까 ?  

ㅜㅜ ? ㅋㅋㅋ ? 

StringBuilder를 쓰는 것도 아니고

표준 출력인데다가 

실행 프로세스 자체를 10번 반복하기 때문에 뭔가 삑사리가 났다면 다른 시행에서도 똑같이 나야 한다. 

 

아 

방문체크를 빼먹었다 

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;

public class SWEA_1267 { // Topological Sort via Stack
	static int[][] board;
	static int[] enters; // 진입 수
	static int V, E;
	// 스택으로 풀려면
	static Stack<Integer> stk;
	static boolean[] visited;
	
	public static void main(String[] args) throws FileNotFoundException {
		Scanner sc = new Scanner(new File("./input_1267.txt"));
		// Scanner sc = new Scanner(System.in);
		
		for(int i = 0; i<10; i++) { // TC 10개
			V = sc.nextInt(); // nodes
			E = sc.nextInt(); // edges
			board = new int[V+1][V+1]; // V는 1부터 
			enters = new int[V+1];
			stk = new Stack<>();
			visited = new boolean[V+1];
			
			for(int j = 0; j<E; j++) {
				int A = sc.nextInt();
				int B = sc.nextInt();
				board[A][B] = 1;
				enters[B]++;
			}
			
			for(int j = 1; j<V+1; j++) {
				if(enters[j] == 0) DFS(j);
			}
			
			System.out.printf("#%d ", i+1);
			while(!stk.isEmpty()){
				System.out.printf("%d ", stk.pop());
			} // while
			
			System.out.println();
		}
	}
	
	static void DFS(int j) {
		visited[j] = true;
		for(int i = 1; i<V+1; i++) { // 방문체크를 안했다 ㅜㅜ ~~
			if(board[j][i] == 1 && !visited[i]) {
				DFS(i);
			}
		}
		stk.add(j);
	}
}

 

풀이 완. ㅋㅋㅋ 

 

 

 

사실 이 문제는 위상 정렬을 Queue / Stack 써서 각각 구현하는 문젠데

Q랑 Stack을 쓰는 그래프 문제? 이거 걍 BFS / DFS라고 보면 됨

여태 BFS / DFS 구조의 핵심이 어떻게 차이나는지 잘 몰라서

BFS로 짜다가도 DFS로 새 버리고 이랬었는데

이 문제를 짜 보니까 좀 알 것 같다 

왼쪽이 BFS, 오른쪽이 DFS

일단 내가 왜 헷갈리고 있었냐면

BFS도 Q를 쓰긴 하지만 어쨌든 실행 자체는 재귀랑 비슷하게 하나의 프로세스를 계속 돈다는 점 때문에 ...

어디서 돌려야 할지 포인트를 못 잡아서 자꾸 재귀함수를 만들게 되고? 

그러다 보니 어찌저찌 답은 나오는데 꼬라지를 보면 DFS였던 적이 많았다.

 

이 문제에서 BFS / DFS form의 가장 큰 차이는

반복을 수행하도록 시키는 포인트가 while(!Empty())문 안에 있느냐 밖에 있느냐 하는 것인데 

BFS의 경우 Q가 빌 때까지 반복하는 문장 안에 Q.add()를 집어넣음으로써 

어떤 조건을 충족하면 그 분기가 계속 반복된다 

이걸 헷갈린다고 밖으로 빼서 재귀로 돌려버리면 그때부터

Q를 쓰기만 하는 DFS가 되는 것 같다

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

정확히는 탐색 시작점을 Q에 넣는 것이고 / while 안에서 탐색을 진행하되 조건을 충족하면 while 안에서 Q.offer를 하는 것

이 포인트 

 

반면에 DFS는 뭐. 

while이고 자시고 조건만 되면 밖에 짜 놓은 메서드 아묻따 돌린다