[DFS] 21937번 - 작업

🔗 문제 링크

백준 21937번 - 작업

📝 풀이

문제에서 주어진 입력 순서대로 작업 순서를 저장하게 되면
dfs 구현시 graph를 2중으로 탐색해야 했다.

public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
public static boolean[] visited;
public static int count = 0;
    
public static void getJobCount(int X) {
	visited[X] = true;
	for(int i = 0; i < graph.size(); i++) {
		ArrayList<Integer> job = graph.get(i);
		for(int j = 0; j < job.size(); j++) {
			if(job.get(j) == X && !visited[i]) {
				count++;
				getJobCount(i);
			}
		}
	}
}

시간 초과 에러가 떴고

작업 순서를 반대로 저장하는 그래프를 구성하여
for 반복문 하나를 사용해서 dfs로 탐색하도록 코드를 수정했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class 작업_21937 {
	
	public static List<Integer>[] graph;
	public static boolean[] visited;
	public static int count = 0;
	
	public static void getJobCount(int X) {
		visited[X] = true;
		
		for(int next: graph[X]) {
			if(!visited[next]) {
				//System.out.println(X + "의 이전 작업은 " + next + "입니다.");
				count++;
				getJobCount(next);
			}
		}
	}
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		graph = new List[N+1];
		visited = new boolean[N+1];
		
		for(int i = 0; i < N+1; i++) {
			graph[i] = new LinkedList<>();
		}
		
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
			graph[n2].add(n1);
		}
		
		st = new StringTokenizer(br.readLine());
		int X = Integer.parseInt(st.nextToken());
		
		getJobCount(X);
		
		System.out.println(count);
	}
}