[Softeer 소프티어] 출퇴근길(자바 풀이)

https://softeer.ai/practice/6248

Softeer - 현대자동차그룹 SW인재확보플랫폼

https://youtu.be/PAihI2CGr-M?si=tPdy_PZHe19dopVh

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

public class Main {
	static int n, m, s, t;
	static List<Integer>[] adj, adjR;

	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()); // 간선의 개수
		adj = new ArrayList[n + 1];
		adjR = new ArrayList[n + 1];
		for (int i = 0; i <= n; i++) {
			adj[i] = new ArrayList<>();
			adjR[i] = new ArrayList<>();
		}
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			adj[x].add(y);
			adjR[y].add(x);
		}
		st = new StringTokenizer(br.readLine());
		int s = Integer.parseInt(st.nextToken());
		int t = Integer.parseInt(st.nextToken());

		int[] fromS = new int[n+1];
		fromS[t] = 1;
		dfs(s, adj, fromS);
		
		int[] fromT = new int[n+1];
		fromT[s] = 1;
		dfs(t, adj, fromT);
		
		int[] toS = new int[n+1];
		dfs(s, adjR, toS);
		
		int[] toT = new int[n+1];
		dfs(t, adjR, toT);
		
		int cnt = 0;
		for(int i = 1; i<=n;i++) {
			if(fromS[i]==1 && fromT[i]==1 && toS[i]==1 && toT[i]==1)
				cnt++;
		}
		
		System.out.println(cnt-2);
	}// main
	
	static void dfs(int now, List<Integer>[] adj, int[] visit) {
		if(visit[now]==1) return;
		visit[now] = 1;
		for(int x : adj[now])
			dfs(x, adj, visit);
	}
}// class