Life Engineering
[BOJ 1043] 거짓말 (Java) 본문
https://www.acmicpc.net/problem/1043
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static List[] adjList=new ArrayList[51];
static List<List<Integer>> parties;
static boolean[] visited;
static int N, M, K, cnt;
static int[] knows;
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
N=Integer.parseInt(st.nextToken());
M=Integer.parseInt(st.nextToken());
st=new StringTokenizer(br.readLine());
K=Integer.parseInt(st.nextToken());
knows=new int[K];
for (int i=0; i<K; i++) {
knows[i]=Integer.parseInt(st.nextToken());
}
int person;
visited=new boolean[N+1];
parties=new ArrayList<List<Integer>>(M);
for (int i=0; i<M; i++) {
st=new StringTokenizer(br.readLine());
cnt=Integer.parseInt(st.nextToken());
parties.add(new ArrayList<Integer>());
for (int j=0; j<cnt; j++) {
person=Integer.parseInt(st.nextToken());
parties.get(i).add(person);
}
for (int j=0; j<cnt; j++) {
int me=parties.get(i).get(j);
if (adjList[me]==null) adjList[me]=new ArrayList<Integer>();
for (int k=0; k<cnt; k++) {
if (me!=parties.get(i).get(k)) {
adjList[me].add(parties.get(i).get(k));
}
}
}
}
for (int i=0; i<K; i++) {
int known=knows[i];
dfs(known);
}
int answer=0;
for (int i=0; i<M; i++) {
for (int j=0; j<parties.get(i).size(); j++) {
if (!visited[parties.get(i).get(j)]) {
answer++;
break;
}
}
}
System.out.println(answer);
}
private static void dfs(int p) {
visited[p]=true;
if (adjList[p]==null) return;
for (int i=0; i<adjList[p].size(); i++) {
int neighbor=(int) adjList[p].get(i);
if (!visited[neighbor]) {
dfs(neighbor);
}
}
}
}
처음엔 뭔가 union-find 같았으나.. 풀이방법이 뭔가 빡 떠오르지 않아서 dfs 로 풀었다.
검색해보니 union-find로 푸는게 더 간단해보인다.
1~N부터 인접 리스트를 만들고, 파티에 같이 참석하는 사람을 인접한 노드로 해서 리스트에 넣어준다.
이후 진실을 아는 사람들의 배열인 knows를 이용해, 그 번호에 대해서 DFS 탐색을 한다.
이웃이면서, 방문하지 않은 노드들을 모두 방문해주고 dfs 탐색 해준다.
이후 한 파티에 참석한 인원 중 미방문 상태가 있으면, 해당 파티에 대해 answer++을 해준다.
그런데 이렇게 하면 너무 복잡한 풀이같아서.. union-find로 푸는게 훨 간단하다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main_BOJ_1043 {
static int N, M, K;
static int[] knows;
static int[] parents;
public static void init() {
for (int i=1; i<=N; i++) {
parents[i]=i;
}
}
public static int find(int i) {
if (parents[i]==i) return i;
return parents[i]=find(parents[i]);
}
public static void union(int a, int b) {
int pa=find(a);
int pb=find(b);
if (pa!=pb) {
parents[pa]=pb;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
N=Integer.parseInt(st.nextToken());
M=Integer.parseInt(st.nextToken());
st=new StringTokenizer(br.readLine());
K=Integer.parseInt(st.nextToken());
knows=new int[K];
parents=new int[N+1];
List<List<Integer>> parties=new ArrayList<>();
init();
for (int i=0; i<K; i++) {
knows[i]=Integer.parseInt(st.nextToken());
}
for (int i=0; i<M; i++) {
st=new StringTokenizer(br.readLine());
int cnt=Integer.parseInt(st.nextToken());
parties.add(new ArrayList<>());
int p=Integer.parseInt(st.nextToken());
parties.get(i).add(p);
int team=find(p);
for (int j=1; j<cnt; j++) {
p=Integer.parseInt(st.nextToken());
union(team, p); //같은 파티->같은 팀으로 묶기
parties.get(i).add(p);
}
}
int answer=0;
for (int i=0; i<M; i++) {
boolean isSameTeam=false;
for (int j=0; j<parties.get(i).size(); j++) {
int p=parties.get(i).get(j);
for (int k=0; k<knows.length; k++) {
if (find(knows[k])==find(p)) { //knows와 같은 그룹에 속할 경우
isSameTeam=true;
break;
}
}
if (isSameTeam) {
break;
}
}
if (!isSameTeam) {
answer++;
}
}
System.out.println(answer);
}
}
union-find 적용해 다시 풀어본 풀이.
'Problem Solving' 카테고리의 다른 글
[BOJ 1107] 리모컨 (Java) (0) | 2022.03.08 |
---|---|
[BOJ 11054] 가장 긴 바이토닉 부분 수열 (Java) (0) | 2022.03.08 |
[BOJ 17836] 공주님을 구해라! (Java) (0) | 2022.03.05 |
[프로그래머스] 방문 길이 (Java) (0) | 2022.03.03 |
[BOJ 1744] 수 묶기 (Java) (0) | 2022.03.03 |