[Baekjoon] 1043_거짓말

Gold IV

문제(출처: https://www.acmicpc.net/problem/1043)

---

< 거짓말 >

 

문제 풀이 & 생각

 

파티 정보를 입력받으면서 파티 정보를 저장하며, 파티에 오는 사람들을 인접 리스트로 저장한다.

그 후에 진실을 아는 사람을 기준으로 bfs 탐색을 통해 진실을 듣는 사람들을 판별한다.

 

인접리스트에는 만약 파티에 1 2 3이 온다면 (1,2) (1,3) (2,3)을 각각 저장한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class _1043_ { // 거짓말
	static boolean visited[], result[];
	static ArrayList<ArrayList<Integer>> arr, party;

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

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		visited = new boolean[n + 1];
		result = new boolean[n + 1];
		arr = new ArrayList<>(); // 인접 리스트
		party = new ArrayList<>(); // 파티
		for (int i = 0; i < n + 1; i++) {
			arr.add(new ArrayList<>());
		}
		for (int i = 0; i < m; i++) {
			party.add(new ArrayList<>());
		}

		st = new StringTokenizer(bf.readLine());
		int num = Integer.parseInt(st.nextToken());
		for (int i = 0; i < num; i++) {
			int idx = Integer.parseInt(st.nextToken());
			result[idx] = true;
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			num = Integer.parseInt(st.nextToken());
			for (int j = 0; j < num; j++) {
				int idx = Integer.parseInt(st.nextToken());
				party.get(i).add(idx);
			}
			for (int j = 0; j < num; j++) {
				for (int k = j + 1; k < num; k++) {
					int a = party.get(i).get(j);
					int b = party.get(i).get(k);
					arr.get(a).add(b);
					arr.get(b).add(a);
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			if (result[i]) {
				visited[i] = true;
				bfs(i);
			}
		}

		int answer = 0;
		for (int i = 0; i < m; i++) {
			boolean flag = false;
			for (int j = 0; j < party.get(i).size(); j++) {
				if (result[party.get(i).get(j)]) {
					flag = true;
					break;
				}
			}
			if (!flag)
				answer += 1;
		}
		System.out.println(answer);
	}

	private static void bfs(int idx) {
		Queue<Integer> queue = new LinkedList<>();
		queue.add(idx);

		while (!queue.isEmpty()) {
			int num = queue.poll();
			for (int i = 0; i < arr.get(num).size(); i++) {
				int next = arr.get(num).get(i);
				if (!visited[next]) {
					visited[next] = true;
					result[next] = true;
					queue.add(next);
				}
			}
		}
	}
}

 

Main

- 사람의 수 (n), 파티의 수 (m) 입력

- visited: 방문 여부

  result: 진실을 아는 사람

  arr : 파티에서 서로 만나는 사람들

  party: 파티 정보

- 진실을 아는 사람 수(num) 입력

- 진실을 아는 사람 수만큼 사람들의 번호를 입력받아 result를 true로 저장

- 파티마다 오는 사람의 수(num) 입력

  파티마다 오는 사람의 수만큼 사람들의 번호를 입력받아 party 정보 저장 및 인접 리스트 저장

- 진실을 아는 사람을 시작으로 하여 bfs 함수 호출

- 파티 정보를 저장해 둔 리스트를 탐색하여 각 파티에서 진실을 아는 사람이 없다면 answer +1

- answer 출력

 

Search

- queue가 빌 때까지 반복 -> num의 인접 리스트 탐색하여 아직 방문하지 않은 곳이라면 방문 표시 / 진실을 아는 사람으로 저장 / queue에 추가 

---

---