BEAKJOON / 백준 - JAVA 1043번 거짓말

2024.09.17기준 - 골드4

728x90

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 지민이가 파티를 가서 이야기를 할 때, 이야기의 진실을 모르는 파티를 간 횟수를 출력하는 문제입니다.

 

문제 접근

1. 이야기의 진실을 아는 사람을 boolean[]로 체크를 해주었습니다.
2. 한 번이라도 진실을 아는 사람을 만나면 true로 체크를 해주어야 합니다.
3. 모든 체크가 끝나고 나서 마지막으로 파티의 인원을 체크해 출력해줍니다.

 

1. 이야기의 진실을 아는 사람을 체크해주었습니다.

// 진실을 아는 사람을 체크하는 배열
boolean[] visit = new boolean[n + 1];
st = new StringTokenizer(br.readLine());
int num = Integer.parseInt(st.nextToken()); // 이야기를 아는 사람의 수

// 진실을 아는 사람 체크
for (int i = 0; i < num; i++) {
    visit[Integer.parseInt(st.nextToken())] = true;
}

 

2. 같이 파티를 간 사람들을 전부 map에다가 저장을 해주었습니다.

// 같이 파티를 간 사람들을 저장하는 map
map = new LinkedHashMap<>();
for (int i = 1; i <= n; i++) {
    map.put(i, new LinkedList<>());
}

int[][] arr = new int[m][];
for (int i = 0; i < m; i++) {
    st = new StringTokenizer(br.readLine()); // 파티의 인원 수
    arr[i] = new int[Integer.parseInt(st.nextToken())]; // 그 파티에 간 사람들 저장하는 배열

    for (int j = 0; j < arr[i].length; j++) {
        arr[i][j] = Integer.parseInt(st.nextToken());
    }

    // 같이 파티를 간 사람들을 map에 저장할 함수 호출
    inputMap(arr[i]);
}

 

한 파티에 참여한 인원이라면 자신을 제외한 모든 인원을 map다가 저장하는 함수를 생성했습니다.

// 같이 파티를 간 사람들을 map에 저장해줄 함수
private static void inputMap(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            if (i != j) {
                map.get(arr[i]).add(arr[j]);
            }
        }
    }
}

 

3. 이야기의 진실을 아는 사람들과 같이 간 인원을 찾기위해 큐를 생성해 진행했습니다.

// 같이 파티를 즐긴 사람을 체크하기 위한 큐
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= n; i++) {
    if (visit[i]) {
        q.add(i);
    }
}

// 같이 파티를 간 사람들을 체크
while (!q.isEmpty()) {
    num = q.poll();

    // 진실을 아는 사람과 같이 파티를 했다면 체크
    for (int membernum : map.get(num)) {
        if (!visit[membernum]) {
            q.add(membernum);
            visit[membernum] = true;
        }
    }
}

1. 처음 입력받은 이야기의 진실을 아는 사람들을 우선적으로 큐에다가 입력을 해주었습니다.
2. 큐에 들어간 인원을 한명씩 뽑아내면서 같이 파티를 간 인원을 map에서 뽑아내 전부 체크를 해주었습니다.

4. 이렇게 이야기의 진실을 아는 인원이 전부 체크되면 파티 하나하나를 확인해 이야기를 할 수 있는 파티의 개수를 출력해줍니다.

boolean check;
int count = 0;
for (int[] party : arr) {
    check = true;

    for (int member : party) {
        // 이 파티에 진실을 아는 사람이 있다면
        if (visit[member]) {
            check = false;
            break;
        }
    }

    // 이 파티에 진실을 아는 사람이 없다면
    if (check) {
        count++;
    }
}

 

 

코드

package Main;

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

public class Main {
	
	static Map<Integer, List<Integer>> map;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 사람의 수
		int m = Integer.parseInt(st.nextToken()); // 파티의 수
		
		// 진실을 아는 사람을 체크하는 배열
		boolean[] visit = new boolean[n + 1];
		st = new StringTokenizer(br.readLine());
		int num = Integer.parseInt(st.nextToken()); // 이야기를 아는 사람의 수
		
		// 진실을 아는 사람 체크
		for (int i = 0; i < num; i++) {
			visit[Integer.parseInt(st.nextToken())] = true;
		}
		
		// 같이 파티를 간 사람들을 저장하는 map
		map = new LinkedHashMap<>();
		for (int i = 1; i <= n; i++) {
			map.put(i, new LinkedList<>());
		}
		
		int[][] arr = new int[m][];
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine()); // 파티의 인원 수
			arr[i] = new int[Integer.parseInt(st.nextToken())]; // 그 파티에 간 사람들 저장하는 배열
			
			for (int j = 0; j < arr[i].length; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
			
			// 같이 파티를 간 사람들을 map에 저장할 함수 호출
			inputMap(arr[i]);
		}
		
		// 같이 파티를 즐긴 사람을 체크하기 위한 큐
		Queue<Integer> q = new LinkedList<>();
		for (int i = 1; i <= n; i++) {
			if (visit[i]) {
				q.add(i);
			}
		}
		
		// 같이 파티를 간 사람들을 체크
		while (!q.isEmpty()) {
			num = q.poll();
			
			// 진실을 아는 사람과 같이 파티를 했다면 체크
			for (int membernum : map.get(num)) {
				if (!visit[membernum]) {
					q.add(membernum);
					visit[membernum] = true;
				}
			}
		}
		
		boolean check;
		int count = 0;
		for (int[] party : arr) {
			check = true;
			
			for (int member : party) {
				// 이 파티에 진실을 아는 사람이 있다면
				if (visit[member]) {
					check = false;
					break;
				}
			}
			
			// 이 파티에 진실을 아는 사람이 없다면
			if (check) {
				count++;
			}
		}
		
		bw.write(Integer.toString(count));
		bw.flush();
		bw.close();
		br.close();
	}
	
	// 같이 파티를 간 사람들을 map에 저장해줄 함수
	private static void inputMap(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr.length; j++) {
				if (i != j) {
					map.get(arr[i]).add(arr[j]);
				}
			}
		}
	}
}