본문 바로가기
Algorithm/Code Tree

[JAVA] 코드트리 메신저

by emgp 2025. 3. 22.

변수 정보

  • $1 ≤ Q (명령의 수) ≤ 100,000$
  • $1 ≤ N (채팅방의 수) ≤ 100,000$
  • $1 ≤ D (주어지는 이진트리의 최대 깊이) ≤ 20$
  • $1 ≤ p_{i} ≤ N$
  • $1 ≤ a_{i}, c, power, c_{1}, c_{2} ≤ N$
  • $c_{1} \neq c_{2}$

 

생각의 흐름

  • 위와 같이 변수가 주어졌을 때, (1) 사내 메신저 준비, (2) 알림망 On/Off 설정, (3) 권한 세기 변경, (4) 부모 채팅방 교환 을 수행해야 됨
  • (2), (3), (4) 명령에 따라 자식의 값이 변하면 부모에게 영향이 가기 때문에, 트리 구조를 사용해야 된다고 생각함
  • 처음 생각했던건 트리, DFS, DP를 사용해서 문제를 풀이해야겠다고 생각했음.
    • 근데 여기서 나의 문제점: 변수를 어떻게 사용할지에 대해는 깊게 고민하지 않았었음
  • 처음에는 단순하게 부모 배열, Authority 세기 배열, 알람 꺼짐 여부만 저장해서 풀이하려고 했으나, 이렇게 된다면 중간에 알림망이 On/Off될 때, 하위 요소까지 한 번에 고려하지 못하게 됨.
  • 따라서 어떤 채팅방이 어떤 채팅방에게 영향을 주는지(알람을 가게 하는지) 저장해야 됨

      

어떤 채팅방 어떤 채팅방에게 영향을 주는지에 대한 정보를 저장하는 법

  • 제일 간단하게 생각하면 채팅방의 개수가 n이라면, int[][] arr = new int[n][n] 배열을 만들어서, arr[i][j]는 i에서 j로 알람을 몇 개 보내는지 저장해도 될 것이라고 생각함
    • 근데 채팅방의 수가 100,000이기 때문에 2차원 배열을 만들면 메모리 초과가 발생해서 그렇게 하면 안됐음
  • 그렇다면 어떻게 이런 정보를 저장할 수 있을까?!
    • 한 채팅방을 기준으로 Authority 만큼 위로 가면서, 부모 채팅방에게 어떻게 영향을 미치는지 저장해야 됨
    • tree[i][j]: i번 채팅방에서 에서 위로 j만큼 갈 수 있는 알람이 몇 개 있는지 저장
  • 예시 (첫 번째 예제에서 8번 채팅방의 authority가 3인 경우)
    • 채팅방의 정보를 입력받은 후, tree 배열에 정보를 채워줘야 됨
    • 만약 8번 채팅방만 생각한다면 ....

   [8][3]에 표시해야 되는걸 [8][2]에 잘못 표시했네요 ㅠㅠ!!

추후 수정하겠습니다.

  • 그림에서 보면 알 수 있듯이
    1. 8번 채팅방는 위로 세 칸 보내는 알람이 한 개 있음
    2. 8번 채팅방의 영향으로 4번 채팅방은 위로 두 칸 보내는 알람이 한 개 생기게 됨
    3. 8번 채팅방의 영향으로 1번 채팅방은 위로 한 칸 보내는 알람이 한 개 생기게 됨
  • 8번 채팅방을 포함해서 모든 채팅방에 대해 알람을 어떻게 보내게 되는지 확인하며 tree 배열을 채우게 된다면 아래 표와 같이 됨
  • 그리고 tree 정보를 채울 때 authority 만큼 올라가면서 부모를 향해 가기 때문에, 부모가 받는 알람의 개수를 세 줄 수 있음

그리고 모든 노드를 고려하고, tree배열을 채우면, 아래처럼 됨

* tree[8][2]에 잘못 표시했습니다ㅠ! tree[8][3]에 체크를 했어야 됐습니다.

추가로 필요한 변수

변수 설명
int[] p p[i]: i 채팅방의 부모 저장
int[] authority authority[i]: i채팅방의 세기 저장
int[] alarm alarm[i]: i채팅방에서 받는 알람의 개수
int[][] tree tree[i][j]: i번 채팅방에서 위로 j만큼 가는 알람의 개수
boolean[] isOff i번 채팅방의 알림망 설정이 꺼져있는지 여부

 

사내 메신저 준비 (명령어: 100)

  • 부모 관계와 Authority에 대한 정보를 입력받고, tree 배열 만들기
  • 주의점
    • 문제에서 트리의 깊이가 최대 20이라고 했기 때문에, Authority 값이 20이 넘지 않도록 해야 됨!
static void step1(StringTokenizer st) {

    for(int i = 1; i < N + 1; i++) {
        int parent = Integer.parseInt(st.nextToken());
        p[i] = parent;
    }

    for (int i = 1; i < N + 1; i++) {

        authority[i] = Integer.parseInt(st.nextToken());
        if(authority[i] > 20) authority[i] = 20; // 권한의 세기가 20이 넘을 때를 주의해야 됨

        int current = i;

        for(int k = authority[i]; k > 0; k--) {
            tree[current][k]++;
            alarm[p[current]]++;
            current = p[current];
        }
    }

}

 

알림망 설정 ON / OFF (명령어: 200)

  • 주어진 채팅방 알림망 설정 바꿔주기 (by toggle_noti(current))
static void step2(StringTokenizer st) {
    // current 채팅방 알림망 설정 바꿔주기
    int current = Integer.parseInt(st.nextToken());
    toggle_noti(current);
}

 

 

public static void toggle_noti(int chat) {

    int mul = isOff[chat] ? 1: -1;

    int parent = p[chat];
    int dis = 1;

    // 상위 채팅으로 이동하며 tree와 alarm값 수정하기
    while (parent != 0) {

        // dis만큼 위로 올라갈수록, parent도 p[p[...[parent]]]가 됨
        alarm[parent] += tree[chat][dis] * mul;

        for(int i = dis + 1; i < MAX_DEPTH + 1; i++) {
            // 위로 몇 칸을 가든, 바로 위에 있는 부모의 알람의 개수에 영향이 감
            alarm[parent] += tree[chat][i] * mul; 
            tree[parent][i - dis] += tree[chat][i] * mul;
        }

        if(isOff[parent]) break; // 알람망이 꺼져 있으면 나가기
        parent = p[parent];
        dis++;
    }

    isOff[chat] = !isOff[chat];
}

toggle_noti 함수 안에 while문이 왜 저렇게 되는지에 대한 그림

 

권한 세기 변경 (명령어: 300)

  • 채팅방의 authority가 변경되기 때문에, 기존 authority로 만들어진 tree 정보를 없애주고, 새로 만들어줘야 됨
  • 채팅방의 알림망이 켜져 있어야 알람이 위로 전달되기 때문에, isOff[n]의 값이 false일 때만 tree, alarm 정보 갱신해주기
    • 별개로 자기 자신에 대한 tree 정보는 꼭 수정해줘야 됨 (tree[n][authority])
static void step3(StringTokenizer st) {
    int n = Integer.parseInt(st.nextToken());
    int power = Math.min(Integer.parseInt(st.nextToken()), 20);

    int origin = authority[n];
    authority[n] = power;

    tree[n][origin]--;

    if (!isOff[n]) { // 알람망이 켜져있는 상태라면, 상위 채팅방에 대한 알람 개수도 수정하기
        int parent = p[n];
        int num = 1;

        while(parent != 0) {
            if(origin >= num) alarm[parent]--;
            if(origin > num) tree[parent][origin - num]--;
            if(isOff[parent]) break;

            parent = p[parent];
            num++;
        }
    }

    tree[n][power]++;

    if (!isOff[n]) {
        int parent = p[n];
        int num = 1;

        while(parent != 0) {
            if(power >= num) alarm[parent]++;
            if(power > num) tree[parent][power - num]++;
            if(isOff[parent]) break;

            parent = p[parent];
            num++;
        }
    }
}

 

 

부모 채팅방 교환 (명령어: 400)

  • 교체하려는 채팅방의 알람망이 꺼져 있는지 확인하고, 바꿔준 다음 이걸 적용해서 다시 tree, alarm 정보를 수정해줘야 됨
    • 알람망이 켜져 있을 때만, 알람이 위로 올라갈 수 있기 때문에 !isOff[n] 일 때만 tree, alarm 정보 수정하기
static void step4(StringTokenizer st) {

    // a, b 채팅방 부모 바꾸기
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());

    boolean bef_noti1 = isOff[a];
    boolean bef_noti2 = isOff[b];


    // 알람망이 켜져 있다면 알림망 끄고, tree, alarm에서 a, b가 미치는 영향 없애주기
    if (!isOff[a]) toggle_noti(a); 
    if (!isOff[b]) toggle_noti(b);

    changeParent(a, b);

    // 알람망이 원래 켜져있는 상태였으면, tree, alarm 값 세팅해주기
    if (!bef_noti1) toggle_noti(a);
    if (!bef_noti2) toggle_noti(b);
}

알림을 받을 수 있는 채팅방 수 조회 (명령어: 500)

  • alarm 배열에 저장한 알람의 개수 출력하기
static void step5(StringTokenizer st) {
    int current = Integer.parseInt(st.nextToken());
    sb.append(alarm[current]).append("\n");
}



전체코드 
import java.io.*;
import java.util.*;

public class DH_코드트리_메신저 {
	static final int MAX_DEPTH = 20;
	static int N, Q;
	static int[] p, authority, alarm;
	static int[][] tree;
	static BufferedReader br;
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
    public static boolean[] isOff;

	
	public static void main(String[] args) throws Exception {
		
		System.setIn(new FileInputStream("./input/코드트리메신저.txt"));
		br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());

		p = new int[N + 1];
		authority = new int[N + 1];
		
		// tree[i][j]: i번 노드가 j 높이만큼 위에까지 전달할 수 있는 채팅의 수
		tree = new int[N + 1][MAX_DEPTH + 1]; 
		alarm = new int[N + 1];
		isOff = new boolean[N + 1];
		
		for(int q = 0; q < Q; q++) {
			st = new StringTokenizer(br.readLine());
			
			int o = Integer.parseInt(st.nextToken());
			
			if(o == 100) step1(st);
			if(o == 200) step2(st);
			if(o == 300) step3(st);
			if(o == 400) step4(st);
			if(o == 500) step5(st);
			
		}
		
		System.out.println(sb);
	}
	
	// 400 
	// 채팅방 부모 바꾸기
	static void step4(StringTokenizer st) {
		
		// a, b 채팅방 부모 바꾸기
		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		
        boolean bef_noti1 = isOff[a];
        boolean bef_noti2 = isOff[b];


        // 알람망이 켜져 있다면 알림망 끄고, tree, alarm에서 a, b가 미치는 영향 없애주기
        if (!isOff[a]) toggle_noti(a); 
        if (!isOff[b]) toggle_noti(b);

        changeParent(a, b);
        
        // 알람망이 원래 켜져있는 상태였으면, tree, alarm 값 세팅해주기
        if (!bef_noti1) toggle_noti(a);
        if (!bef_noti2) toggle_noti(b);
	}
	
    // 채팅의 알림 상태를 토글합니다.
    public static void toggle_noti(int chat) {
    	
    	int mul = isOff[chat] ? 1: -1;
    	
        int parent = p[chat];
        int dis = 1;
        
        // 상위 채팅으로 이동하며 tree와 alarm값 수정하기
        while (parent != 0) {
        	
        	// dis만큼 위로 올라갈수록, parent도 p[p[...[parent]]]가 됨
        	alarm[parent] += tree[chat][dis] * mul;
        	
        	for(int i = dis + 1; i < MAX_DEPTH + 1; i++) {
        		// 위로 몇 칸을 가든, 바로 위에 있는 부모의 알람의 개수에 영향이 감
        		alarm[parent] += tree[chat][i] * mul; 
        		tree[parent][i - dis] += tree[chat][i] * mul;
        	}
        	
        	if(isOff[parent]) break; // 알람망이 꺼져 있으면 나가기
        	parent = p[parent];
            dis++;
        }
            
        isOff[chat] = !isOff[chat];
    }
	
	static void changeParent(int a, int b) {
		int tmp = p[a];
		p[a] = p[b];
		p[b] = tmp;
	}
	
	// 200
	// 채팅방 설정 바꿔주기
	static void step2(StringTokenizer st) {
		// current 채팅방 알림망 설정 바꿔주기
		int current = Integer.parseInt(st.nextToken());
		toggle_noti(current);
	}
	
	// 300
	// 권한 세기 변경
	static void step3(StringTokenizer st) {
		int n = Integer.parseInt(st.nextToken());
		int power = Math.min(Integer.parseInt(st.nextToken()), 20);
		
		int origin = authority[n];
		authority[n] = power;
		
		tree[n][origin]--;
		
        if (!isOff[n]) { // 알람망이 켜져있는 상태라면, 상위 채팅방에 대한 알람 개수도 수정하기
			int parent = p[n];
			int num = 1;
			
			while(parent != 0) {
				if(origin >= num) alarm[parent]--;
				if(origin > num) tree[parent][origin - num]--;
		        if(isOff[parent]) break;
				
				parent = p[parent];
				num++;
			}
		}
		
		tree[n][power]++;
		
        if (!isOff[n]) {
			int parent = p[n];
			int num = 1;
			
			while(parent != 0) {
				if(power >= num) alarm[parent]++;
				if(power > num) tree[parent][power - num]++;
                if(isOff[parent]) break;
				
				parent = p[parent];
				num++;
			}
		}
	}

	static void step5(StringTokenizer st) {
		int current = Integer.parseInt(st.nextToken());
		sb.append(alarm[current]).append("\n");
	}
	
	static void step1(StringTokenizer st) {
		
		for(int i = 1; i < N + 1; i++) {
			int parent = Integer.parseInt(st.nextToken());
			p[i] = parent;
		}
		
        for (int i = 1; i < N + 1; i++) {
        	
            authority[i] = Integer.parseInt(st.nextToken());
            if(authority[i] > 20) authority[i] = 20; // 권한의 세기가 20이 넘을 때를 주의해야 됨
            
            int current = i;
            
            for(int k = authority[i]; k > 0; k--) {
            	tree[current][k]++;
            	alarm[p[current]]++;
            	current = p[current];
            }
        }

	}
}

해설을 보고도 잘 이해가 되지 않았던 문제,,, ㅠ ㅠ 아직 난,, 멀었다!!!!!!!!1

저작자표시

'Algorithm > Code Tree' 카테고리의 다른 글

[JAVA] 나무박멸  (0) 2024.03.26

관련글

티스토리툴바