1043번: 거짓말(Java)

 한 파티에 진실을 아는 사람이 있다면 나머지 사람들에게도 진실을 알리면 된다고 생각했다. 그러면 진실을 절대 알 수 없는 사람들만 참가했던 파티 수를 얻을 수 있기 때문이다. 

 

 

 

 

가장 먼저 person class를 만들었다. 각 person은 아이디(사람 번호), 진실을 아는지 여부, 친구들을 가지고 있다.

친구들을 만든 이유는 거짓말이라는 것을 알았을 때 같이 파티에 참가했던 친구들에게 소문은 퍼뜨려야 하기 때문이다. 

public static class person
{
    int id;//아이디
    boolean know;//진실을 아는지 여부
    Stack<Integer> friends;//친구들
    person(int id, boolean know)
    {
        this.id = id;
        this.know = know;
        friends = new Stack<>();
    }
    //소문을 퍼뜨리는 함수
    void spread()
    {
        this.know = true;//거짓말을 안다고 바꾼다
        while(!friends.isEmpty())//자신을 제외한 모든 친구들에게 알린다
        {
            int i = friends.pop();
            if(i != this.id)
            {
                personList[i].spread
            }
        }
    }
    //친구들 추가한다
    void addFriend(int id)
    {
        if(id != this.id)
        {
            friends.push(id);
        }
    }
    //진실을 아는지 모르는지 반환한다
    boolean getKnow()
    {
        return this.know;
    }
    //진실을 아는지 모르는지 설정한다
    void setKnow(boolean know)
    {
        this.know = know;
    }
}

 

그다음으로 전역 변수로 person 배열을 하나 만들었다.

public static  person[] personList;//사람들

main함수 안에서 사람 수를 입력받으면 사람 수와 동일한 크기로 초기화할 것이다.

 

 

 

이제 main 함수이다.

입력받은 사람 수에 따라 person 배열을 초기화하고 파티 수, 진실을 아는 사람의 수를 입력받는다.

각 파티(Stack)들을 가지고 있는 Stack인 partyList를 선언한다. partyList 안에는 파티(Stack)가 들어가며, 파티(Stack)에는 해당 파티에 참여한 사람의 번호를 넣을 것이다. 

결과 변수에는 우선 파티 수를 넣고, 입력과 소문 퍼뜨리기가 끝나면 나중에 하나씩 뺄 것이다.

find 변수는 해당 파티에서 진실을 아는 사람이 나왔는지 여부를 저장할 것이며, 진실을 아는 사람이 해당 파티에 참가했었다면, 해당 파티에 참여했던 모두에게 각자의 친구들에게 수문을 퍼뜨리라고 할 것이다.

Scanner scanner = new Scanner(System.in);
personList = new person[scanner.nextInt()];//인원수에 맞게 사람들을 선언한다
int partyNum = scanner.nextInt();//파티 수를 입력받는다
int knowsNum = scanner.nextInt();//진실을 아는 사람 수를 입력받는다
Stack<Stack<Integer>> partyList = new Stack<>();//파티들을 담을 변수를 선언한다(해당 파티에 참여한 사람들의 id를 가진 Stack 들을 가진 Stack)
int result = partyNum;//결과 = 파티 수
boolean find;//해당 파티에서 진실을 아는 사람이 나왔는지 여부

 

 

 

우선 모든 사람들을 초기화하고 진실을 모른다고 설정했다.

//모든 사람들을 초기화하고 진실을 모른다고 초기화한다
for(int i = 0; i<personList.length; i++)
{
    personList[i] = new person(i, false);
}

 

그다음 진실을 아는 사람을 입력받으면서 setKnow() 함수를 호출한다.

//진실을 아는지 모르는지 설정한다
void setKnow(boolean know)
{
    this.know = know;
}

 

 

이제 반복문을 돈다.

반복 내용은 다음과 같다.

1. 파티에 참여하는 사람 수를 입력받는다.

2. Stack<Integer> 변수를 하나 만들고 초기화한다.

3. find = false로 설정한다(찾으면 true를 대입할 것이기 때문)

4. 파티에 온 사람들을 입력받으며 만약 해당 사람이 진실을 알고 있다면 find = true를 한다. 또한 2번에서 만든 Stack이 비어있지 않다면 2번에서 만든 Stack의 top에 있는 id를 가진 사람과 방금 입력받은 사람은 서로 친구를 맺는다. 왜냐하면 서로 친구를 맺는다면 누가 소문을 퍼뜨렸을 때 해당 파티에 참여했던 사람들 뿐만 아니라 해당 파티에 참여했던 사람들 중 다른 파티에도 참여했던 사람이 있다면 그 파티에 있던 사람들에게도 소문을 퍼뜨릴 수 있기 때문이다. 마지막으로 2번에서 만든 Stack에 방금 입력받은 id를 push 한다.

5. 만약 find가 true 라면 2번에서 만든 Stack에 있는 모든 id를 순회하며 해당 id를 가지고 있는 사람에게 소문을 퍼뜨리라고 한다.

6. partyList에 2번에서 만든 Stack을 push 한다.

이걸 코드로 구현하면 다음과 같다.

//파티들을 입력받는다
for(int i = 0; i<partyNum; i++)
{
    int peopleNum = scanner.nextInt();//파티에 참여하는 사람 수를 입력받는다
    Stack<Integer> temp = new Stack<>();//파티를 만든다
    find = false;//우선 파티에 진실을 아는 사람은 없다고 가정한다
    //파티에 온 사람들을 입력받는다
    for(int j = 0; j<peopleNum; j++)
    {
        int id = scanner.nextInt();//사람의 id를 입력받는다
        if(personList[id-1].getKnow())//해당 id를 가진 사람이 진실을 아는 사람이면 find = true
        {
            find = true;
        }
        if(!temp.isEmpty())//파티에 한 명이라도 있다면 서로 친구를 맺는다
        {
            personList[id-1].addFriend(temp.peek());//입력받은 id를 가진 사람은 이전에 왔던 사람 중 가장 최근에 온 사람을 친구에 추가한다
            personList[temp.peek()].addFriend(id-1);//이전에 왔던 사람 중 가장 최근에 온 사람 또한 입력받은 id를 가진 사람을 친구로 추가한다
        }
        temp.push(id-1);//입력받은 id를 파티에 온 사람 목록에 추가한다
    }
    if(find)//만약 파티에 온 사람 중 진실을 아는 사람이 한 명이라도 있다면
    {
        temp.forEach((p)->personList[p].spread());//해당 파티에 참석한 전원에게 친구들에게 진실을 알리게 한다
    }
    partyList.push(temp);//해당 파티를 파티들 Stack 에 추가한다
}

이 과정을 생각하기가 정말 힘들었다. 어떻게 하면 다른 파티에 같이 참여했던 사람들에게도 영향을 줄 수 있을지 생각하다가 서로 친구를 맺으면 서로가 서로에게 진실을 알릴 수 있을 것이라는 판단을 했다.

 

 

 

 

 

 

이제 result를 정할 차례이다. partyList가 빌 때까지 반복한다.

Stack <Integer>를 하나 만들고 partyList.pop()을 넣는다. 

해당 Stack 안에 진실을 아는 사람이 있는지 검사하고, 있다면 result--를 해 준다.

//파티들 Stack 이 빌 때까지 반복한다
while(!partyList.isEmpty())
{
    Stack<Integer> temp = partyList.pop();//파티를 pop 한다
    //pop 한 파티가 빌 때까지 반복한다
    while(!temp.isEmpty())
    {
        if(personList[temp.pop()].know)//한 명이라도 진실을 아는 사람이 있다면 result-- 후 break;
        {
            result--;
            break;
        }
    }
}

 

이렇게 하면 진실을 아는 사람이 한 명도 없는 파티의 개수가 result에 저장된다. result를 출력하면 끝이다.

 

 

 

 

 

결과 코드

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

public class Main
{
    public static  person[] personList;//사람들
    //사람 클래스
    public static class person
    {
        int id;//아이디
        boolean know;//진실을 아는지 여부
        Stack<Integer> friends;//친구들
        person(int id, boolean know)
        {
            this.id = id;
            this.know = know;
            friends = new Stack<>();
        }
        //소문을 퍼뜨리는 함수
        void spread()
        {
            this.know = true;//거짓말을 안다고 바꾼다
            while(!friends.isEmpty())//자신을 제외한 모든 친구들에게 알린다
            {
                int i = friends.pop();
                if(i != this.id)
                {
                    personList[i].spread();
                }
            }
        }
        //친구들 추가한다
        void addFriend(int id)
        {
            if(id != this.id)
            {
                friends.push(id);
            }
        }

        //진실을 아는지 모르는지 반환한다
        boolean getKnow()
        {
            return this.know;
        }
            //진실을 아는지 모르는지 설정한다
            void setKnow(boolean know)
            {
                this.know = know;
            }
    }
    public static void main(String[] args) throws IOException
    {
        Scanner scanner = new Scanner(System.in);
        personList = new person[scanner.nextInt()];//인원수에 맞게 사람들을 선언한다
        int partyNum = scanner.nextInt();//파티 수를 입력받는다
        int knowsNum = scanner.nextInt();//진실을 아는 사람 수를 입력받는다
        Stack<Stack<Integer>> partyList = new Stack<>();//파티들을 담을 변수를 선언한다(해당 파티에 참여한 사람들의 id를 가진 Stack 들을 가진 Stack)
        int result = partyNum;//결과 = 파티 수
        boolean find;//해당 파티에서 진실을 아는 사람이 나왔는지 여부


        //모든 사람들을 초기화하고 진실을 모른다고 초기화한다
        for(int i = 0; i<personList.length; i++)
        {
            personList[i] = new person(i, false);
        }

        //진실을 아는 사람들을 설정한다
        for(int i = 0; i<knowsNum; i++)
        {
            personList[scanner.nextInt()-1].setKnow(true);
        }

        //파티들을 입력받는다
        for(int i = 0; i<partyNum; i++)
        {
            int peopleNum = scanner.nextInt();//파티에 참여하는 사람 수를 입력받는다
            Stack<Integer> temp = new Stack<>();//파티를 만든다
            find = false;//우선 파티에 진실을 아는 사람은 없다고 가정한다
            //파티에 온 사람들을 입력받는다
            for(int j = 0; j<peopleNum; j++)
            {
                int id = scanner.nextInt();//사람의 id를 입력받는다
                if(personList[id-1].getKnow())//해당 id를 가진 사람이 진실을 아는 사람이면 find = true
                {
                    find = true;
                }
                if(!temp.isEmpty())//파티에 한 명이라도 있다면 서로 친구를 맺는다
                {
                    personList[id-1].addFriend(temp.peek());//입력받은 id를 가진 사람은 이전에 왔던 사람 중 가장 최근에 온 사람을 친구에 추가한다
                    personList[temp.peek()].addFriend(id-1);//이전에 왔던 사람 중 가장 최근에 온 사람 또한 입력받은 id를 가진 사람을 친구로 추가한다
                }
                temp.push(id-1);//입력받은 id를 파티에 온 사람 목록에 추가한다
            }
            if(find)//만약 파티에 온 사람 중 진실을 아는 사람이 한 명이라도 있다면
            {
                temp.forEach((p)->personList[p].spread());//해당 파티에 참석한 전원에게 친구들에게 진실을 알리게 한다
            }
            partyList.push(temp);//해당 파티를 파티들 Stack 에 추가한다
        }

        //파티들 Stack 이 빌 때까지 반복한다
        while(!partyList.isEmpty())
        {
            Stack<Integer> temp = partyList.pop();//파티를 pop 한다
            //pop 한 파티가 빌 때까지 반복한다
            while(!temp.isEmpty())
            {
                if(personList[temp.pop()].know)//한 명이라도 진실을 아는 사람이 있다면 result-- 후 break;
                {
                    result--;
                    break;
                }
            }
        }
        System.out.println(result);
    }
}