[백준]1953_팀배분_DFS(BFS도 가능)

🔗 문제링크 🔗

1953번: 팀배분

---

🌟 생각 흐름 🌟

우선 문제를 풀기 위해서 싫어하는 사람들과의 표기를 그래프를 통해서 진행했다

그래프를 그린 후 한 노드에서 시작한 경우 현재 노드와 다음노드만 다른 팀이면 가능하다고 생각했다

그리고 그 다음노드에서의 다음노드가 서로 다른 팀이면 가능하다는 식으로 dfs로 구현하였다

그래서 한 노드에서 시작한후 현재 깊이가 짝수이면 청팀, 홀수 이면 백팀에 넣도록 코드를 구현하였다

예를 들어 1,2가 서로를 싫어하고 2,3이 서로를 싫어하는 경우 

 ↔️ : 서로 싫어하는 경우 포기

1️⃣ ↔️ 2️⃣ ↔️ 3️⃣ 와  같이 표기할 수 있고

1에서 시작한 경우 아래와 같다.

1️⃣ : 청팀(깊이 0)

2️⃣ : 백팀(깊이 1)

3️⃣ : 청팀(깊이 2)

---

🍳 코드 🍳

	package 백준.graph;
	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.ArrayList;
	import java.util.Collections;
	import java.util.List;
	import java.util.StringTokenizer;
	public class boj_1953_팀배분 {
	private static boolean[] visited;
	private static List<Integer>[] hates;
	private static final List<Integer>[] teams = new List[2];
	private static final StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	int n = Integer.parseInt(br.readLine());
	//init
	visited = new boolean[n + 1];
	hates = new List[n + 1];
	for (int i = 0; i < 2; i++) {
	teams[i] = new ArrayList<>();
	}
	for (int i = 0; i <= n; i++) {
	hates[i] = new ArrayList<>();
	}
	//input
	for (int i = 1; i <= n; i++) {
	st = new StringTokenizer(br.readLine());
	int cnt = Integer.parseInt(st.nextToken());
	for (int j = 0; j < cnt; j++) {
	hates[i].add(Integer.parseInt(st.nextToken()));
	}
	}
	//solution
	for (int i = 1; i <= n; i++) {
	if (!visited[i]) {
	dfs(i, 0);
	}
	}
	//output
	setTeam(teams[0]);
	setTeam(teams[1]);
	System.out.println(sb);
	}
	private static void setTeam(List<Integer> team) {
	Collections.sort(team);
	sb.append(team.size()).append("\n");
	for (Integer now : team) {
	sb.append(now).append(" ");
	}
	sb.append("\n");
	}
	private static void dfs(int start, int nowCnt) {
	if (!visited[start]) {
	visited[start] = true;
	teams[nowCnt % 2].add(start);
	for (Integer hate : hates[start]) {
	dfs(hate, nowCnt + 1);
	}
	}
	}
	}

view raw boj_1953_팀배분.java hosted with ❤ by GitHub