🔗 문제 링크
📌 문제 설명
- N명의 사람이 있고, M개의 파티가 열린다.
- 어떤 사람이 진실을 알고 있다면, 그 사람이 참석한 모든 파티에서는 거짓말을 할 수 없다.
- 각각의 파티에는 여러 사람이 참여할 수 있으며, 서로 연결될 수 있다.
- 최대한 많은 파티에서 거짓말을 할 수 있는 경우의 수를 구하는 문제.
💡 접근 방법
1️⃣ 그래프 탐색 (DFS) 활용
- 진실을 아는 사람들을 노드로 설정하고, 연결된 사람들을 한 그룹으로 묶는다.
- 연결된 그룹은 하나의 집합 (Union-Find) 으로 간주하고, DFS 탐색을 통해 진실을 아는 그룹을 확장한다.
- 각 파티에서 진실을 아는 사람이 한 명이라도 포함되면 거짓말이 불가능하다.
📝 코드 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static StringTokenizer st;
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static int N, M;
private static List<Integer> knowMans = new ArrayList<>();
private static List<Integer>[] connInfo;
private static List<Integer>[] parties;
public static void main(String[] args) throws IOException {
setting();
System.out.println(getResult());
}
private static int getResult() {
boolean[] visited = new boolean[N + 1];
// 진실을 아는 사람들을 DFS로 연결된 모든 사람에게 확장
for (Integer knowMan : knowMans) {
if (visited[knowMan]) continue;
visited[knowMan] = true;
dfs(knowMan, visited);
}
// 각 파티를 확인하면서 진실을 말해야 하는지 체크
int cnt = 0;
for (int i = 0; i < M; i++) {
if (isVisited(i, visited)) cnt++;
}
return cnt;
}
private static boolean isVisited(int i, boolean[] visited) {
for (Integer x : parties[i]) {
if (visited[x]) return false;
}
return true;
}
private static void dfs(Integer knowMan, boolean[] visited) {
for (Integer conn : connInfo[knowMan]) {
if (visited[conn]) continue;
visited[conn] = true;
dfs(conn, visited);
}
}
private static void setting() throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
parties = new List[M];
for (int i = 0; i < M; i++) {
parties[i] = new ArrayList<>();
}
connInfo = new List[N + 1];
for (int i = 0; i <= N; i++) {
connInfo[i] = new ArrayList<>();
}
st = new StringTokenizer(br.readLine());
int cnt = Integer.parseInt(st.nextToken());
for (int i = 0; i < cnt; i++) {
knowMans.add(Integer.parseInt(st.nextToken()));
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
cnt = Integer.parseInt(st.nextToken());
for (int j = 0; j < cnt; j++) {
parties[i].add(Integer.parseInt(st.nextToken()));
}
// 각 파티에서 연결된 사람들끼리 그래프 형성
for (int j = 0; j < parties[i].size(); j++) {
for (int k = j + 1; k < parties[i].size(); k++) {
connInfo[parties[i].get(j)].add(parties[i].get(k));
connInfo[parties[i].get(k)].add(parties[i].get(j));
}
}
}
}
}🔍 코드 설명
🔹 그래프 탐색을 활용한 풀이
-
입력값 처리
connInfo[i]: 사람들의 관계를 그래프로 저장.parties[i]: 각 파티에 속한 사람들의 리스트.knowMans: 진실을 알고 있는 사람들.
-
DFS로 연결된 모든 사람 찾기
knowMans리스트에 있는 사람들을 기준으로 DFS 수행하여 연결된 모든 사람을 방문 처리.
-
거짓말이 가능한 파티 찾기
- 모든 파티를 순회하며 진실을 아는 사람이 없는 경우만 카운트.
🛠 최적화 및 개선 가능성
✅ 1️⃣ DFS 탐색 최적화
- 현재
dfs()에서 이미 방문한 노드는visited[]처리를 하지만,
→ 재귀 호출 전에 바로 return하면 불필요한 탐색을 줄일 수 있음.
private static void dfs(Integer knowMan, boolean[] visited) {
if (visited[knowMan]) return; // 추가 최적화
visited[knowMan] = true;
for (Integer conn : connInfo[knowMan]) {
dfs(conn, visited);
}
}🔽 변경 후 탐색 시간 단축 가능!
✅ 2️⃣ BFS로 변경 가능
DFS 대신 BFS를 사용하면 코드가 조금 더 직관적이 될 수 있음.
private static void bfs(Integer start, boolean[] visited) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int cur = queue.poll();
for (Integer next : connInfo[cur]) {
if (!visited[next]) {
visited[next] = true;
queue.add(next);
}
}
}
}🚀 DFS보다 BFS가 유리한 경우
- 그래프가 깊고, 불필요한 재귀 호출이 많아질 경우 BFS를 사용하면 메모리 초과 방지 가능.
⏳ 시간복잡도 분석
O(N + M): 입력값 처리O(N + M): DFS 탐색O(MN): 모든 파티에서 진실을 아는 사람 확인
총 시간 복잡도: O(N + M + MN) ≈ O(NM)
→ N, M 최대 50이므로 충분히 가능!
🎯 결론
✅ DFS 또는 BFS를 활용하여 그래프 탐색 문제를 해결!
✅ 진실을 아는 사람과 연결된 그룹을 탐색한 후, 거짓말 가능한 파티를 카운트!
✅ 최적화를 적용하면 불필요한 탐색을 줄일 수 있음!
멋있는 사람 - 일단 하자