뒤죽박죽 코딩 이야기

2021년 7월 26일 월요일 - 여전히 덥구나

오늘 올려볼 문제는 1043번 거짓말 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘은 문제를 둘러보다 문제가 꽤 재밌어보여서 가지고왔다.

근데 어렵다..

입력 예제

백준 문제 중에서 입력 예제가 매우 많은 편인 문제다!

입력 예제를 간략히 설명하자면

1. 첫째줄에는 n(파티에 참가하는 인원)과 m(파티의 개수)가 주어진다.
2. 둘째줄에는 진실을 아는 사람의 명수가 주어지고 그 명수만큼 같은 줄에 띄어쓰기로 구분되어 사람들의 번호가 주어진다.
3. 셋째줄부터 m + 3줄까지는 파티에 참여하는 사람의 명수가 주어지고 그 명수만큼 같은 줄에 띄어쓰기로 구분되어 사람들의 번호가 주어진다.

풀이 및 코드

사이트에 들어가서 해당 문제의 분류를 보면 알겠지만 그래프 기법을 사용해서 문제를 푸는 것이 정석이다.

하지만 난! 오늘은 매우 비효율적이지만 그래프를 사용하지 않는 방법으로 문제를 풀 것이다!
알고리즘적으로는 별로 도움이 안된다는 말...

먼저 풀이를 설명하기 전에 문제를 한 번 봐보자.

1. 지민이의 진실을 알고 있는 사람이 파티에 참여할 경우 지민이는 진실을 말한다.
2. 파티에 참가하는 사람 중 저번 파티에서는 진실을 듣고 이번 파티에서는 거짓말을 듣는 상황이 생겨서는 안된다.
3. 이 때 지민이가 거짓말을 할 수 있는 파티의 최대 개수를 구하는 것이 이 문제이다.

문제만 보면 직감에 의한 오류를 범하기 쉽다.

바로 이전 파티에서 거짓을 듣고 이번 파티에서 진실을 듣는 경우에 대해서는 생각하기 쉽지 않기 때문이다.

이전 파티에 대해서는 그저 이전 파티로만 생각하고 처리하게 되면 이러한 오류를 저지르게 된다.

그러면 이 때 막막하기 시작할 것이다.

그럼 대체 어떤 방법을 사용해야 하는 것인가... 아까 말한 그래프를 사용하는 방법이 가장 좋은 방법이 아닌가?

물론 그래프를 사용하는 것이 공부도 되고 좋긴 하겠지만... 구현이 너무 귀찮다....

그렇기에 나는 그냥 무식하게 여러번 비교하는 방법을 사용하기로 했다!!

코드와 같이 설명하겠다!

풀이코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 진실을 알고 있는 사람들을 저장하는 배열(알고 있으면 true 아니면 false)
        boolean[] know_truth = new boolean[55];

        String[] input_nums = br.readLine().split(" ");

        int n = Integer.parseInt(input_nums[0]), m = Integer.parseInt(input_nums[1]);

        // 입력을 저장하는 배열(여러번 비교할 것이기 때문에 저장 필수)
        String[] arr = new String[m];

        // 입력으로 주어지는 진실을 알고 있는 사람
        String[] truth_nums = br.readLine().split(" ");

        // know_truth배열에서 true로 만들어주기
        for(int i = 1; i < truth_nums.length; i++)
        {
            know_truth[Integer.parseInt(truth_nums[i])] = true;
        }

        // 입력을 받고 진실을 알고 있는 사람과 같은 파티에 참가한 사람도 진실을 아는 것으로 바꾸는 과정
        for(int i = 0; i < m; i++)
        {
            arr[i] = br.readLine();
            String[] input = arr[i].split(" ");
            boolean flag = false;

            for(int j = 1; j < input.length; j++)
            {
                if(know_truth[Integer.parseInt(input[j])])
                {
                    flag = true;
                    break;
                }
            }

            if(flag)
            {
                for(int j = 1; j < input.length; j++)
                {
                    know_truth[Integer.parseInt(input[j])] = true;
                }
            }

        }

        // 위 과정에서 입력을 받는 것만 빼고 같은 과정을 50번 반복한다. (파티의 수가 최대 50개가 될 수 있기 때문)
        for(int a = 0; a < 50; a++)
        {
            for(int i = 0; i < m; i++)
            {
                String[] input = arr[i].split(" ");
                boolean flag = false;

                for(int j = 1; j < input.length; j++)
                {
                    if(know_truth[Integer.parseInt(input[j])])
                    {
                        flag = true;
                        break;
                    }
                }

                if(flag)
                {
                    for(int j = 1; j < input.length; j++)
                    {
                        know_truth[Integer.parseInt(input[j])] = true;
                    }
                }

            }
        }

        int result = 0;

        // 진실을 아는 사람은 모두 구해졌으므로 파티에서 진실을 아는 사람이 없을 때만 result를 증가시킨다.
        for(int i = 0; i < m; i++)
        {
            String[] input = arr[i].split(" ");
            boolean flag = true;

            for(int j = 1; j < input.length; j++)
            {
                if(know_truth[Integer.parseInt(input[j])])
                {
                    flag = false;
                    break;
                }
            }

            if(flag)
            {
                result++;
            }
        }

        bw.write(result + "\n");
        bw.flush();

    }

}

제출 화면

사실 내가 푼 방식은 시간복잡도 O(n^3)으로 만약 입력 개수가 500 이상이 된다고 하면 이 방법을 쓰기에는 어려움이 많을 것이다.

하지만 오늘 이 포스팅을 쓴 이유는 문제 해결을 위해서 정석적인 길말고도 다른 길도 있다는 것을 알려주기 위해서 포스팅을 한 것이다.

알고리즘 문제뿐만이 아닌 현실의 문제에서도 다른 길이 있을 수 있으니 정석이 너무 힘들다면 조금 다른 방법도 생각해보는 것도 나쁘지 않을 것 같다.