[백준 10159] 저울 / 자바 / dfs

#문제         

레벨: G4
알고리즘: dfs 
풀이시간: 30분
힌트 참조 유무:

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

---

#문제 풀이        

 

그래프로 나타내면 문제풀이 하기 더 수월하다.

위 그래프는 자기보다 가벼운 노드를 나타낸 거다.

아래 그래프는 자기보다 무거운 노드를 나타낸 거다.

 

두 번의 dfs를 통해 자신보다 무거운 노드들, 가벼운 노드들을 알아내면 정답을 알 수 있다.

 

1번 노드를 예를 들어보자

dfs(1,lighter)를 하면  1 -> 2  -> 3 -> 4     =  3(자기자신제외)

dfs(1,heavier)를 하면  1  -> x =  0(자기자신제외)

6(N) -  1(자기 자신) - 3 - 0 =  2

 

 

 

---

#풀이 코드      

import java.util.*;
import java.io.*;

public class Main {
    static ArrayList<Integer>[] heavier;
    static ArrayList<Integer>[] lighter;
    static boolean[] visited;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        heavier = new ArrayList[N + 1];
        lighter = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            heavier[i] = new ArrayList<>();
            lighter[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            heavier[a].add(b);  //자신보다 무거운 노드 담기
            lighter[b].add(a);   // 자신보다 가벼운 노드 담기
        }

        for (int i = 1; i <= N; i++) {
            visited = new boolean[N + 1];
            int heavierCount = dfs(i, heavier) - 1; // 자기 자신 제외
            
            visited = new boolean[N + 1];
            int lighterCount = dfs(i, lighter) - 1; // 자기 자신 제외
            
            System.out.println(N - 1 - heavierCount - lighterCount);
        }
    }

    static int dfs(int node, ArrayList<Integer>[] graph) {
        visited[node] = true;
        int count = 1;

        for (int next : graph[node]) {
            if (!visited[next]) {
                count += dfs(next, graph);
            }
        }

        return count;
    }
}

 

---

#비슷한 유형     

https://jsw5913.tistory.com/178

[백준 2458] 키 순서 / 자바 / dfs