[SWEA] 1267. 작업순서 (Java)

문제

SW Expert Academy

 

풀이

0. 문제 해석

위상 정렬을 이용하는 문제이다.

 

위와 같은 그래프가 존재할 때,

 

1. 차수 (자신에게 들어오는 정점 수) 가 0인 정점을 제거하는 방법

2. DFS의 역순 탐색 방법

 

두가지 방법으로 위상정렬을 구현할 수 있다.

 

이 글에서는 2번으로 해결하였다.

역순으로 DFS를 구현하기 위해서는

위와 같이 그래프의 방향을 전부 반대로 한 후 아무곳에서나 dfs로 탐색하고, 역순(stack) 으로

출력하면 된다.

 

1. 그래프 생성

그래프를 생성할 때

입력받은 간선의 방향을 반대로 생성한다.

 

2. DFS

이제 깊이우선 탐색으로

방문하지 않은 정점들을 탐색해주고

탐색한 역순으로 출력해준다.

 

3. 전체 코드

// [SWEA] 1267. 작업순서 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
	static int v; // 정점의 총 수
	static int e; // 간선의 총 수
	static int[][] graph; // 관계 그래프
	static int[] visit; // 방문 그래프
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	for(int t = 1; t <= 10; t++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		
    		v = Integer.parseInt(st.nextToken());
    		e = Integer.parseInt(st.nextToken());
    		graph = new int[v+1][v+1];
    		visit = new int[v+1];
    		st = new StringTokenizer(br.readLine());
    		
    		// 그래프 반대로 연결
    		for(int i = 0; i < e; i++) {
    			int x = Integer.parseInt(st.nextToken());
        		int y = Integer.parseInt(st.nextToken());
    			graph[y][x] = 1;
    		}
    		
    		System.out.print("#" + t + " ");
    		
    		for(int i = 1; i <= v; i++) {
    			if(visit[i] == 0) {
    				dfs(i);
    			}
    		}
    		System.out.println();
    	}
    }
    
    // 제일 나중에 도착한 지점이 먼저 나옴 (stack)
    public static void dfs(int x) {
    	visit[x] = 1;
    	
    	for(int i = 1; i <= v; i++) {
    		if(graph[x][i] == 1 && visit[i] == 0) {
    			dfs(i);
    		}
    	}
    	
    	System.out.print(x + " ");
    }
}