1043번 - 거짓말

1️⃣ BFS

 

✏️ 풀이 과정

BFS 혹은 DFS를 통해 빠르게 해결할 수 있는 문제지만 입력이 특수하게 들어오기 때문에 정점끼리 연결하는 부분이 조금 복잡합니다.

 

아래 코드에서는 문제 해결을 크게 두 파트를 통해 해내고 있습니다. 한 가지는 BFS를 통해 진실을 알고있는 사람과 그 사람들과 같은 파티에 참석한 사람 그리고 그 사람들과 같은 파티에 참석한 사람... 들을 모두 방문처리 하는 것입니다. 다른 하나는 방문처리된 배열을 통해서 다시 파티 정보를 순회하며 방문 처리된 사람이 하나도 없을 경우 거짓말을 해도 되는 파티라고 판단하여 카운팅해주는 것입니다.

 

인접 리스트를 사용해서 연결 관계를 표시했고 그 방법은 먼저 파티의 정보를 배열로 받은 이후(모든 파티의 정보를 기억해두기 위해 이차원 배열을 사용합니다.) 이중 for문을 통해 한 파티의 모든 참가자에 대해 자신 외의 모든 참가자와 연결 링크를 만드는 것입니다.

 

이렇게 인접 리스트를 완성하고 처음에 입력으로 받은 진실을 아는 사람 각각마다 BFS를 실행해주면 연관된 모든 사람을 방문표시할 수 있습니다.

 

방문 표시가 완료되면 저장한 파티 정보를 다시 순회하며 방문표시가 된 사람이 파티에 있을 경우 라벨링된 for문 이름을 사용해 continue하고 없을 경우 카운트를 1씩 올려줍니다.

 

위 과정을 거치면 문제에서 요구하는 거짓말을 해도 되는 파티의 개수를 얻게 됩니다.

 

💻 코드

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

public class Main {
	
	// 정점(사람)을 표현하는 클래스
	static class Node {
		int v;
		Node link;
		
		public Node(int v, Node link) {
			this.v = v;
			this.link = link;
		}
	}
	
	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());
		// 파티 상태를 저장하는 배열
		int[][] party = new int[M][];
		st = new StringTokenizer(br.readLine());
		// 진실을 아는 사람 수
		int num = Integer.parseInt(st.nextToken());
		// 진실을 아는 사람을 표시하는 배열
		int[] banned = new int[num];
		for (int i = 0; i < num; i++) {
			banned[i] = Integer.parseInt(st.nextToken());
		}
		// 파티 참석인수
		int person;
		// 파티 참석 관계 표현을 위한 인접 리스트
		Node[] adjList = new Node[N+1];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			person = Integer.parseInt(st.nextToken());
			// 이차원 배열  party의 열의 길이를 참여 인수에 맞춰 각각 다르게 선언 
			party[i] = new int[person];
			for (int j = 0; j < person; j++) {
				party[i][j] = Integer.parseInt(st.nextToken());
			}
			// 참석 인원들끼리 인접 리스트에 연결관계 표시
			for (int j = 0; j < person; j++) {
				for (int k = 0; k < person; k++) {
					// 자기 자신은 인접리스트에 표시하지 않고 건너뜀
					if(j == k) {
						continue;
					}
					// 탐색을 위해 양방향 모두 표시
					adjList[party[i][j]] = new Node(party[i][k], adjList[party[i][j]]);
					adjList[party[i][k]] = new Node(party[i][j], adjList[party[i][k]]);
				}
			}
		}
		// BFS를 위한 Queue 선언
		LinkedList<Integer> q = new LinkedList<>();
		int cur;
		// 방문 표시를 위한 배열
		boolean[] visited = new boolean[N+1];
		// BFS를 진실을 아는 인원 수만큼 실행
		for (int i = 0; i < num; i++) {
			// 진실을 아는 인원부터 BFS 시작
			q.offer(banned[i]);
			// 해당 인원 방문 표시
			visited[banned[i]] = true;
			// BFS 실행
			while(!q.isEmpty()) {
				cur = q.poll();
				// 같이 파티에 참석한 인원 중 미방문인 경우 모두 visited 표시하고 큐에 넣는다.
				for(Node n=adjList[cur];n!=null;n=n.link) {
					if(!visited[n.v]) {
						visited[n.v] = true;
						q.offer(n.v);
					}
				}
			}
		}
		// 답을 위한 카운팅 변수 선언
		int cnt = 0;
		// 탈출을 위해 for문에 라벨 지정
		loop:
		// 모든 파티에 대해 진실을 아는 인원(과 연결된 인원까지)이 있는 지 파악
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < party[i].length; j++) {
				// 해당 파티에 방문처리된 인원이 있으면 카운트를 올리지 않고 건너뜀
				if(visited[party[i][j]]) {
					continue loop;
				}
			}
			// 한 명도 방문처리되지 않았으면 카운팅
			cnt++;
		}
		// 답 출력
		System.out.println(cnt);
		br.close();
	}
}