알고리즘
백준 1953번 팀 배분 (JAVA)
박카스마시며코딩
2022. 10. 5. 22:55
https://www.acmicpc.net/problem/1953
1953번: 팀배분
첫줄에는 청팀의 사람의 수를 출력하고, 그리고 둘째 줄에는 청팀에 속한 사람들을 오름차순으로 나열한다. 그리고 셋째 줄과 넷째 줄은 위와 같은 방법으로 백팀에 속한 인원의 수, 백팀에 속
www.acmicpc.net
저는 DFS를 통해 해당 문제를 해결하였습니다.
DFS를 통해 각 인원을 팀에 넣고 해당 경우의 수가 되는지를 확인하고 된다면 출력하였습니다.
package BOJ.dfs;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.function.Function;
public class BOJ_1953 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
Function<String,Integer> stoi = Integer::parseInt;
int n = stoi.apply(st.nextToken());
Set<Integer>[] hate = new HashSet[n+1];
for(int i = 1 ; i <= n ; i++){
hate[i] = new HashSet<>();
st = new StringTokenizer(br.readLine());
int cnt = stoi.apply(st.nextToken());
for(int j = 0 ; j < cnt ; j++){
int num = stoi.apply(st.nextToken());
hate[i].add(num);
}
}
boolean[] choice = new boolean[n+1];
dfs(1,choice,n,hate);
}
private static boolean dfs(int depth, boolean[] choice,int n,Set<Integer>[] hate){
if(depth == n+1){
int cnt = 0;
for(int i = 1 ; i <= n ; i++){
if(choice[i]){
cnt++;
}
}
System.out.println(cnt);
for(int i = 1 ; i <= n ; i++){
if(choice[i]){
System.out.print(i+" ");
}
}
System.out.println();
System.out.println(n-cnt);
for(int i = 1 ; i <= n ; i++){
if(!choice[i]){
System.out.print(i+" ");
}
}
return true;
}
boolean firstTeam = true;
boolean secondTeam = true;
for(int i = 1 ; i < depth ; i++){
if(choice[i] && hate[i].contains(depth)){
firstTeam = false;
}
if(!choice[i] && hate[i].contains(depth)){
secondTeam = false;
}
}
if(firstTeam){
choice[depth] = true;
if(dfs(depth+1,choice,n,hate)){
return true;
}
}
if(secondTeam){
choice[depth] = false;
if(dfs(depth+1,choice,n,hate)){
return true;
}
}
return false;
}
}