[JAVA] 백준 1043번 【G4.거짓말】

문제

1043번: 거짓말

 

풀이

1️⃣ 플로이드 알고리즘을 이용한 풀이

💡 떠오른 Idea

이 문제는 파티별로 바로 체크를 할 수 없는 문제이고, 모든 파티의 정보를 처리한 다음에 개수를 구할 수 있다.

그 이유는

예제 처럼

4 5
1 1
1 1
1 2
1 3
1 4
2 4 1

위와 같이 주어졌을 때,
4번째 파티인
1 4
에서는 4번이 진실을 모를것 같지만

5번째 파티에서 진실을 아는 1번이 4번에게 알려 줄 수 있기 때문이다.

따라서, 순차적으로 판단할 수 없다.

내가 생각한 전략은 지민이를 0번으로 두고 나머지 1번부터 N번의 사람들의 그래프를 정의하고

진실을 아는 번호와 지민이의 번호인 0 번을 먼저 연결해준다.

그리고, 각 파티별로 만나는 사람들 간에 연결을 해준다.

마지막으로 플로이드 알고리즘을 통해 처리를 하고 지민이의 번호인 0 번과 거리와 상관없이 연결되는 노드라면 진실을 알게되는 사람임을 알 수 있다.

그리고 파티별로 순회하면서 0번과 연결된 번호가 하나라도 없는 경우에 카운팅하는 방식을 사용하였다.

 

public class Main {
    static final int MAX = 100;

    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]);

        // 지민이 번호는 0 으로 가정
        int[][] graph = new int[N + 1][N + 1];

        for (int r = 0; r < N + 1; r++) {
            for (int c = 0; c < N + 1; c++) {
                if (r != c) {
                    graph[r][c] = MAX;
                }
            }
        }

        List<List<Integer>> parties = new ArrayList<>();

        input = br.readLine().split(" ");
        int numOfKnow = Integer.parseInt(input[0]);

        // 진실을 아는 사람은 지민이 번호 (0) 과 연결
        for (int i = 1; i <= numOfKnow; i++) {
            graph[0][Integer.parseInt(input[i])] = 1;
            graph[Integer.parseInt(input[i])][0] = 1;
        }

        for (int i = 0; i < M; i++) {
            input = br.readLine().split(" ");
            List<Integer> party = new ArrayList<>();

            int numOfPeople = Integer.parseInt(input[0]);

            // 같은 파티에 참석하는 사람들끼리 연결
            for (int j = 1; j <= numOfPeople; j++) {
                party.add(Integer.parseInt(input[j]));
                for (int k = j + 1; k <= numOfPeople; k++) {
                    graph[Integer.parseInt(input[j])][Integer.parseInt(input[k])] = 1;
                    graph[Integer.parseInt(input[k])][Integer.parseInt(input[j])] = 1;
                }
            }
            parties.add(party);
        }

        // 플로이드 알고리즘 사용
        for (int m = 0; m < N + 1; m++) {
            for (int u = 0; u < N + 1; u++) {
                for (int v = 0; v < N + 1; v++) {
                    graph[u][v] = Math.min(graph[u][v], graph[u][m] + graph[m][v]);
                }
            }
        }


        int ans = 0;

        // 지민이 번호인 0번에서 특정 번호로 가는 경로가 존재하지 않아야 진실을 아는 사람이 없는 파티
        for (List<Integer> party : parties) {
            boolean flag = true;
            for (int num : party) {
                if (graph[0][num] != MAX) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

 

결과