[백준 1043번 / Java] 거짓말

문제 링크

Gold 4

 

https://www.acmicpc.net/problem/1043

1043번: 거짓말

 

 

 

첫 풀이

크게 시간, 메모리 고려를 하지 않아도 될 것 같아보여서 뇌를 빼고 풀어보려고 했다. (사실 Union Find에 자신이..)

 

단순 String배열을 활용하고, List에 String배열을 저장하여 정답을 도출하려고 했고, 문제에서 제공하는 테스트케이스를 만족해서 됐다!!! 라고 생각했다.

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

public class Main {

    static int[] trueMan;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        trueMan = new int[N + 1];

        String tmp = br.readLine();
        String[] tmpArr = tmp.split(" ");
        int tmpLen = tmpArr.length;

        for (int i = 1; i < tmpLen; i++) {
            int man = Integer.parseInt(tmpArr[i]);
            trueMan[man]++;
        }

        List<String[]> list = new ArrayList<>();

        for (int i = 0; i < M; i ++) {
            tmp = br.readLine();
            tmpArr = tmp.split(" ");
            tmpLen = tmpArr.length;

            for (int j = 1; j < tmpLen; j ++) {
                int man = Integer.parseInt(tmpArr[j]);
                boolean chk = false;
                for (int k = 0; k < trueMan.length; k ++) {
                    if (trueMan[man] > 0) {
                        chk = true;
                        break;
                    }
                }

                if (chk) {
                    for (int k = 1; k < tmpLen; k ++) {
                        man = Integer.parseInt(tmpArr[k]);
                        trueMan[man]++;
                    }
                }
            }

            String[] newArr = new String[tmpLen - 1];
            for (int j = 1; j < tmpLen; j ++) {
                newArr[j - 1] = tmpArr[j];
            }
            list.add(newArr);
        }

        for (String[] arr : list) {
            for (String str : arr) {
                int num = Integer.parseInt(str);
                boolean chk = false;
                for (int i = 0; i < trueMan.length; i ++) {
                    if (trueMan[num] > 0) {
                        M--;
                        chk = true;
                        break;
                    }
                }
                if (chk) break;
            }
        }
        System.out.println(M);
    }
}

 

 

역시 골딱이 정도 되면 단순 뇌뺴기로는 안되나보다

 

 

 

 

두번째 풀이

뇌가 빠졌을 때 무엇이 부족했을까 생각해서 열거해보았다.

 

아무리 코테문제라지만 너무 복잡해서 가독성이 꽝임

그러다보니 어디를 고쳐야하는지 쉽게 감이 오지 않음

입력하면서 체크할 게 아니라 입력을 다 받고 체크하는 게 나을 것 같음

문제 풀이를 위한 것이라면 잘 다루지 못하는 Union Find여야 하는가. BFS로도 충분히 풀 수 있어보임

 

1. input 값을, 진실을 말해야만 하는 사람과 파티에 참여하는 사람을 나눠서 받았다. (한 컬렉션으로 받아도 무관할 듯)

List<String> trueMan = new ArrayList<>();
for(int i = 1; i < inputLen; i ++) {
    trueMan.add(input[i]);
}

List<int[]> tmp = new ArrayList<>();
for(int i = 0; i < M; i ++) {
    input = br.readLine().split(" ");
    inputLen = input.length;

    int[] arr = new int[N + 1];
    for (int j = 1; j < inputLen; j ++) {
        arr[Integer.parseInt(input[j])]++;
    }
    tmp.add(arr);
}

2. BFS를 위해 Queue를 선언하고 진실을 말해야만 하는 사람을 넣었다.

Queue<Integer> queue = new LinkedList<>();
for(String s : trueMan) {
    queue.add(Integer.parseInt(s));
}

3. BFS 구현을 위한 파티일자, 사람에 대한 체크를 위한 boolean 배열을 사용한다.

int answer = M;
boolean[] visited = new boolean[N + 1];
boolean[] visitedM = new boolean[M];

4. BFS라고 하지만, Queue에 새로운 값이 들어올 때, 모든 파티 일자의 인원에 대해 거짓말을 할 수 있는지 여부를 모두 파악해야 했다.

while(!queue.isEmpty()) {
    int now = queue.poll();
    visited[now] = true;

    for(int i = 0; i < M; i ++) {
        int[] tmpArr = tmp.get(i);
        if(tmpArr[now] > 0 && !visitedM[i]) {
            for(int j = 1; j < tmpArr.length; j ++) {
                if(tmpArr[j] == 1 && !visited[j]) {
                    queue.add(j);
                    visited[j] = true;
                }
            }
            answer--;
            visitedM[i] = true;
            if(answer == 0) {
                System.out.println(answer);
                return;
            }
        }
    }
}

 

 

전체 코드는 아래와 같다.

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

public class Main {

    static int[] trueMan;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");

        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);

        input = br.readLine().split(" ");
        int inputLen = input.length;

        if(inputLen == 1) {
            System.out.println(M);
            return;
        }

        List<String> trueMan = new ArrayList<>();
        for(int i = 1; i < inputLen; i ++) {
            trueMan.add(input[i]);
        }

        List<int[]> tmp = new ArrayList<>();
        for(int i = 0; i < M; i ++) {
            input = br.readLine().split(" ");
            inputLen = input.length;

            int[] arr = new int[N + 1];
            for (int j = 1; j < inputLen; j ++) {
                arr[Integer.parseInt(input[j])]++;
            }
            tmp.add(arr);
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for(String s : trueMan) {
            queue.add(Integer.parseInt(s));
        }

        int answer = M;
        boolean[] visited = new boolean[N + 1];
        boolean[] visitedM = new boolean[M];

        while(!queue.isEmpty()) {
            int now = queue.poll();
            visited[now] = true;

            for(int i = 0; i < M; i ++) {
                int[] tmpArr = tmp.get(i);
                if(tmpArr[now] > 0 && !visitedM[i]) {
                    for(int j = 1; j < tmpArr.length; j ++) {
                        if(tmpArr[j] == 1 && !visited[j]) {
                            queue.add(j);
                            visited[j] = true;
                        }
                    }
                    answer--;
                    visitedM[i] = true;
                    if(answer == 0) {
                        System.out.println(answer);
                        return;
                    }
                }
            }
        }
        System.out.println(answer);
    }
}