백준 10159 : 저울

https://www.acmicpc.net/problem/10159

10159번: 저울

[ 문제풀이 ]

문제를 해석해보면 결국 내가 비교할 수 없는 물건의 개수는 N - 1(나) - (내가 방문할 수 있는 정점 + 나에게 방문하는 정점)이다.따라서 dfs를 통해 모든 정점을 탐색하면서 확인해주면 쉽게 해결할 수 있다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	
	static int N, M;
	static int[] count;
	static boolean[][] visit;
	static List<Integer>[] edges;
	
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			N = Integer.parseInt(br.readLine());
			M = Integer.parseInt(br.readLine());
			visit = new boolean[N + 1][N + 1];
			count = new int[N + 1];
			edges = new ArrayList[N + 1];
			for (int i = 0; i <= N; ++i) {
				count[i] = N - 1;
				edges[i] = new ArrayList<>();
			}
			for (int i = 0; i < M; ++i) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				int to = Integer.parseInt(st.nextToken());
				int from = Integer.parseInt(st.nextToken());
				edges[from].add(to);
			}
			
			for (int i = 1; i <= N; ++i) dfs(i, i);
			for (int i = 1; i <= N; ++i) bw.write(count[i] + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static void dfs(int v, int s) {
		for (int nv : edges[v]) {
			if (visit[s][nv]) continue;
			visit[s][nv] = true; //내가 방문할 수 있는 정점
			count[s]--;
			visit[nv][s] = true; //나에게 방문할 수 있는 정점
			count[nv]--;
			dfs(nv, s);
		}
	}
}