SEG + DFS 응용법 and pro문제_디렉토리카운트

디렉토리카운트

 

최상위 디렉토리 7 보다 작은 하위 디렉토리의 개수 6

 

5보다 작은 디렉토리 개수 2

4보다 작은 디렉토리 개수 1

총합은 9

 

입력 ) 테스트 케이스 T

다음줄 디렉토리의 개수 N ,최상위 디렉토리의 수

다음줄 N-1개가 상위디렉토리 하위디렉토리 관계(상위 디렉토리 번호 , 하위 디렉토리 번호)

2 <= N <=3000

2

7 7  (7개의 디렉토리와 최상위 디렉토리는 7번노드이다.)

7 6

7 5

1 3

5 1

4 2

7 4

5 4

4 1

1 2

4 5

5 3

 

출력 예)

#1 9

#2 4

 

TC 1.

 

 

일단 이 문제가 좀 약점이 있다. DFS를 하려면 재귀를 돌려야 하는데 만약 1~2만개 정도의 편향된 그래프가 들어온다면

메모리 OUT이 걸리기 때문에 N의 개수가 좀 작다.

그래서 N이 3000이니깐 그냥 모든 노드에 대해서 DFS 때려서 구하면 되지 않나?????

 

이렇게 말이다. 어차피 3000x3000 걸릴턴데....

 

import java.util.*;
import java.io.*;
import java.math.*;
 
public class D210421_pro190615_디렉토리카운트_brute {
 
    static int sum = 0;
    static ArrayList<ArrayList<Integer>> edge;
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("input2.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int tc = Integer.parseInt(br.readLine());
        
        for(int z = 1 ; z <= tc ;z++) {
            //long beforeTime = System.currentTimeMillis();
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int root = Integer.parseInt(st.nextToken());
            
            sum = 0;
            edge = new ArrayList<ArrayList<Integer>>(n+1);
            for(int i = 0 ; i <= n; i++)
                edge.add(new ArrayList<Integer>());
            
            for(int i = 0 ; i < n-1 ; i++) {
                st = new StringTokenizer(br.readLine());
                int ss = Integer.parseInt(st.nextToken());
                int ee = Integer.parseInt(st.nextToken());
                edge.get(ss).add(ee);
            }
            
            for(int i = 1 ; i <= n ; i++)
                go(i, i);
            //long afterTime = System.currentTimeMillis();
            //System.out.println("#"+z+" "+sum + " " +(afterTime-beforeTime));
            
        }        
    }
    
    static void go(int base, int cur_node) {
        //System.out.println(base+ " " + cur_node);
        if(base > cur_node)
            sum++;
        
        int size = edge.get(cur_node).size();
        for(int i = 0 ; i < size ; i++)
            go(base, edge.get(cur_node).get(i));
    }
}
 

이렇게 말이다.

 

 

근데 프로문제가 이렇게 간단하게 나올리는 없고 이 문제가 무엇을 원하는가를 찾아보는데 중점을 두었다.

 

 

아무튼 그러면 만들어진 전체 그래프를 기준으로 어떻게 하면 

각 탐색마다 N이 아닌 log2N 을 해줄 수 있는지 고민해야 한다.

 

 

루트노드는 주어졌으니 그래프 그리는건 어렵지 않고 음........

 

 

 

여기서 이것을 볼 수 있어야 한다. 일단 그래프 하나 그려보자.

 

직관적으로 보면 이게 당연한 거지만 내가 만일 DFS로 4번노드(끝)까지 탐색했었을 때 이렇게 연결 되어있는 것으로 

4 보다 작은 하위 디렉토리의 개수를 어떻게 짤 것인가???

0개인것 알겠는데 말이야......

 

그것보다 더 잘 봐야 하는것은

 

그리고 6번 탐색을 끝내고 5번으로 되돌아 왔을 때 이것이 하위 디렉토리 수가 1개인건 어떻게 알 수 있을까?

저장된 노드라면 1,3,2,6,5 가 있고 하위 디렉토리를 알려면 4를 알아야 하는데.... 모른단 말이야.....

5번노드에서 또 DFS식 탐색???? 그러면 O(N)인데?????

 

 

 

 

 

이 아이디어를 잡아야 한다.

 

 

 

상위 디렉토리 V1 보다 작은 하위 디렉토리의 개수 N개 는

---->

하위 디렉토리 V2 보다 큰 상위 디렉토리의 개수 N개  (크거나 같다 해봤자 어차피 같은 번호의 노드는 없을꺼니 pass)

 

이렇게 바꿀 수 있어야 한다.!!!!!!!!!

 

 

잠시만 수학적 역으로는 맞는 말이긴 하지만 이게 진짜 된다고??????

 

해보자

어??????? 답이 같네?????

 

일단 로직을 생각해 보자.

4번노드 탐색 시 4번노드보다  큰 상위 디렉토리 수 를 구한다면 밑으로 내려오면서 

1 3 2 6 5 4 를 어디다가 저장해놨을터니깐 이 저장한 것들중에서 4보다 큰건 5,6이니깐 답은 2개 라는건 알겟는데......

 

1 3 2 6 5 4 여기서 5,6을 그냥 뽑을라면 N만큼 또 탐색해야 하자나???

 

 

여기서 필요한게 세그먼트 트리이다.

 

세그먼트는 수의 추가, 원하는 수의 추출 둘다 log2N이 걸린다.

 

세그먼트 트리의 원리는 검색하면 널려있으니깐 찾아서 일단 보면 되고......

 

 

아무튼 저 1 3 2 6 5 4 를 세그를 통해서 해보자

 

일단 1 3 2 6 5 4 DFS탐색하면서 update 해보자.

일단 최하위 노드인 4번까지 오면 세그트리는 이런 상태일 것이다.

여기서 1~6을 가리키는 노드는 현재 탐색되어진 1~6번 노드의 개수의 합이다.

 

좀 이해가 안가는가???? 그러면 문제의 노드 기준으로 다시 한번 설명한다.

그러면 이 노드 기준으로 DFS 탐색을 으로 3번노드에 도착해왔다라는건

7,5,1,3번노드를 품고 있는 상태이므로 (4,2는 DFS 재귀로부터 빠져나왔지 않았는가)

이런 세그트리 상태일 것이다.

 

 

 

 

 

 

그러면 4번노드 기준

하위 디렉토리 V2 보다 큰 상위 디렉토리의 개수 N개  (크거나 같다 해봤자 어차피 같은 번호의 노드는 없을꺼니 pass)

이것을 생각하면

5번노드 ~6번노드가 품고 있는 수(sum) 을 찾으면 될것이 아닌가? 그러면 2가 나올 것이다.

이렇게 말이다

 

이제 4번노드를 빠져나오고 5번트리 로 되돌아 오면 이 세그트리에서 

update(4번트리 , -1)을 해주니깐

 

이런 상태일 것이고 5번노드 기준

6번노드 ~6번노드가 품고 있는 수(sum) 을 찾으면 될것이 아닌가? 그러면 1이 나올 것이다.

 

이것을 이렇게 풀면 된다.

여기서 sum이나 update나 세그먼트 트리 특성상 전부 log2N의 시간이 걸린다.

 

그러면 이제 이것을 짜주면 된다.

 

 

 

 

 

 

import java.util.*;
import java.io.*;
import java.math.*;
 
public class D210421_pro190615_디렉토리카운트_seg {
 
    static ArrayList<ArrayList<Integer>> edge;
    static int v;
    static int root;
    static int[] segarr;
    static int[] cnt;
    static int ans;
    
    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream("input2.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int tc = Integer.parseInt(br.readLine().trim());
        
        for(int z = 1 ; z <= tc ; z++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            v = Integer.parseInt(st.nextToken());
            root = Integer.parseInt(st.nextToken());
            
            segarr = new int[v*4];
            cnt = new int[v+1];
            ans = 0;
            edge = new ArrayList<ArrayList<Integer>>();
            for(int i = 0 ; i <= v ; i++)
                edge.add(new ArrayList<Integer>());
            
            for(int i = 1 ; i < v ; i++) {
                st = new StringTokenizer(br.readLine());
                int s = Integer.parseInt(st.nextToken());
                int e = Integer.parseInt(st.nextToken());
                edge.get(s).add(e);
            }
            
            init(root);
            
            System.out.println("#"+z+" " +ans);
        }
        
    }
    
    static void update(int node, int start, int end, int target, int diff) {
        if(target < start || end < target)
            return;
        
        segarr[node] += diff;
        
        if(start == end)
            return;
        
        int mid = (start+end)/2;
        update(node*2, start, mid , target, diff);
        update(node*2+1, mid+1, end, target, diff);
    }
    
    static int getSum(int node, int start, int end , int left , int right) {
        if(end < left || right < start)
            return 0;
        
        if(left <= start && end <= right)
            return segarr[node];
        
        return getSum(node*2, start , (start+end)/2, left, right) + getSum(node*2+1, (start+end)/2+1 , end, left, right);
    }
    
    static void init(int cur_node) {
        update(1,1,v,cur_node, 1);
        
        int size = edge.get(cur_node).size();    
        for(int i = 0 ; i < size ; i++)
            init(edge.get(cur_node).get(i));
        
        
        update(1,1,v,cur_node, -1);
        System.out.println(cur_node + " " + Arrays.toString(segarr));
        ans += getSum(1, 1, v, cur_node, v);
    }
}