[코드트리] 악수와 전염병의 상관관계 2

난이도는 어려움. 푸는데 40분정도 걸렸고,, 초반에 잘못 생각했던 분기처리를 마지막까지 남겨놔서 여러번 틀렸다.

문제는 다음과 같다.

 

N명의 개발자들이 있으며, T번에 걸쳐 t초에 x개발자가 y개발자와 악수를 나눈 정황이 주어집니다. 1명의 개발자가 처음에 이 전염병을 옮기기 시작한 것이 확실해 졌고, 개발자가 이 병에 감염된 후에는 정확히 K번의 악수 동안만 전염병을 옮기게 되고, 그 이후부터는 전염병에 걸려있지만 새로 옮기지는 않게 됩니다. 개발자들의 악수에 대한 정보와 처음 전염병에 걸려 있는 개발자의 번호 P가 주어졌을 때, 모든 악수를 진행한 이후에 최종적으로 누가 전염병에 걸리게 되었는지를 알아내는 프로그램을 작성해보세요. 단, 전염된 사람끼리 만나도 전염시킨 것으로 간주해야 함에 유의합니다. 예를 들어 전염된 x 개발자와 전염된 y 개발자끼리 악수를 해도 전염병을 옮기게 되는 횟수에 포함시켜야 합니다.

 

입력 형식

첫 번째 줄에 정수 N, K, P, T가 각각 공백을 사이에 두고 주어집니다.

두 번째 줄부터는 T개의 줄에 걸쳐 각 줄마다 t, x, y에 대한 정보가 공백을 사이에 두고 주어집니다. 이는 t초에 x 개발자와 y 개발자가 악수를 나눴음을 의미하고, x, y 값은 항상 다르게 주어짐을 가정해도 좋습니다. 또한, 입력으로 주어지는 t값은 모두 다름을 가정해도 좋습니다.

• 2 ≤ N ≤ 100
• 1 ≤ K ≤ 250
• 1 ≤ P ≤ N
• 1 ≤ T ≤ 250
• 1 ≤ t ≤ 250

출력 형식

첫 번째 줄에 N명의 개발자에 대한 최종 감염 여부를 첫 번째 개발자부터 순서대로 N 번째 개발자까지 공백없이 출력합니다. 각 개발자 마다 출력해야 할 값은 0 또는 1이며, 0은 음성을 1은 양성을 뜻합니다.

 

입출력 예제

예제1

입력:

4 2 2 3
7 1 2 
5 2 3
6 2 4

 

출력:

0111

 

예제 설명

4명의 개발자 중에 한 사람당 최대 2번 이내의 악수에 대해서만 전염을 시킬 수 있고, 처음 2번 개발자만 감염되어있는 상황입니다. 시간 순서대로 보면 먼저 5초 때, 2번과 3번이 악수를 하게 되므로 3번은 감염이 됩니다.
6초 때에는 2번과 4번이 악수를 하게 되므로 4번이 감염이 됩니다. 7초 때 1번과 2번이 악수를 하게 되지만, 2번은 최대 2번의 악수까지만 전염을 시킬 수 있으므로 이때는 전염을 시킬 수 없게 됩니다. 따라서 최종적으로 전염이 된 사람은 2, 3, 4번 개발자 입니다.

 

내 코드

import java.util.*;

class Dev{
    int num; //개발자 번호
    int count;// 감염시킬 수 있는 횟수, -1이면 감염된적 없음. 0이면 감염됐었고 횟수를 다 사용함

    Dev(int num, int count){
        this.num = num;
        this.count = count;
    }
}

class Node implements Comparable<Node>{
    int t; //시간
    int x; //x개발자
    int y; //y개발자

    Node(int t, int x, int y){
        this.t = t;
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Node node){
        return this.t - node.t;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); //개발자 수
        int K = sc.nextInt(); //전염병을 옮기는 횟수
        int P = sc.nextInt(); //개발자의 번호
        int T = sc.nextInt(); //테스트케이스

        Dev[] devArr = new Dev[N]; //개발자 배열
        for(int i = 0; i < N; i++){
            devArr[i] = new Dev(i+1, i+1 == P ? K : -1); // 최초감염자는 감염횟수로 K를 넣고 나머지는 -1을 넣는다. 최초감염자일때만 감염시킬 수 있는 횟수를 충전해주기 위해.
        }

        Node[] nodeArr = new Node[T];
        for(int i = 0; i < T; i++){
            nodeArr[i] = new Node(sc.nextInt(), sc.nextInt(), sc.nextInt()); //테스트케이스 배열에 담는다.
        }
        Arrays.sort(nodeArr); //배열 시간순 정렬

        for(Node node : nodeArr){
            if(devArr[node.x-1].count > 0){ //감염시킬 수 있는 횟수가 -1보다크고(감염됐었고) 0보다큰(감염시킬수있고)
                if(devArr[node.y-1].count == -1){
                    devArr[node.y-1].count = K; //상대방이 감염된적이 없으면 감염시키고 감염횟수를 충전해준다.
                }
                devArr[node.x-1].count--; //내 감염가능횟수를 1 줄인다. 대신 0보다 줄이지는 않는다. -1이되면 비감염자가 되기 때문
            }else if(devArr[node.y-1].count > 0){
                if(devArr[node.x-1].count == -1){
                    devArr[node.x-1].count = K;
                }
                devArr[node.y-1].count--;
            }
        }

        for(Dev dev : devArr){
            System.out.print(dev.count > -1 ? 1 : 0);
        }
    }
}