[Baekjoon] 21937_작업

Silver I

문제(출처: https://www.acmicpc.net/problem/21937)

---

< 작업 >

 

문제 풀이 

 

B 작업을 하기 위해 바로 이전에 A 작업을 해야 한다면 작업 B를 하기 위해 먼저 해야 하는 일을 찾기 위해 거꾸로 저장한다. 그래프를 저장할 때 B에 A를 저장한다. 그 후 dfs를 사용하여 답을 구한다. 

 

 

 my solution (Java)

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

public class _21937_ { // 작업
	static ArrayList<ArrayList<Integer>> list;
	static boolean visited[];
	static int result;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		list = new ArrayList<>();
		visited = new boolean[n + 1];
		result = 0;

		for (int i = 0; i < n + 1; i++) {
			list.add(new ArrayList<>());
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list.get(b).add(a);
		}

		int start = Integer.parseInt(bf.readLine());

		visited[start] = true;
		dfs(start);

		System.out.println(result);
	}

	private static void dfs(int start) {
		for (int i = 0; i < list.get(start).size(); i++) {
			if (!visited[list.get(start).get(i)]) {
				visited[list.get(start).get(i)] = true;
				result += 1;
				dfs(list.get(start).get(i));
			}
		}
	}
}

변수)
n, m : 작업할 개수, 작업 순서 정보의 개수
list : 그래프
visited : 방문 여부
result : 작업 X를 하기 위해 먼저 해야 하는 일의 개수
a, b : 작업 A, B
start : 오늘 반드시 끝내야 하는 작업 X

 

작업 A, B를 입력받으면 ArrayList B에 A를 추가한다. 그래프를 다 만들면 dfs 함수를 호출한다.

dfs에서 자신과 연결된 작업을 아직 하지 않았다면 작업을 하고 dfs를 호출을 반복한다.

 

작업 X를 하기 위해 먼저 해야 하는 일의 개수인 result를 출력한다.

---

---