[Java] 백준 1765번 : 닭싸움 팀 정하기

1. 문제

https://www.acmicpc.net/problem/1765

1765번: 닭싸움 팀 정하기

 

 

 

2. 풀이 과정

가장 많은 팀이 되는 경우 = 친구는 무조건 같은 팀이어야 하므로, 친구끼리만 같은 팀이고 나머지는 다 다른 팀

따라서, 친구만 찾아서 연결지어주면 된다.

 

 

친구인 경우

1) 친구의 친구는 친구
2) 원수의 원수는 친구

 

조건 1에서는 dfs로 친구의 친구의 친구 ... 까지 다 찾아야 한다.

하지만, 원수의 경우 자신의 원수의 원수만 친구이다. 즉, 나-친구-원수-원수는 친구의 친구지만, 내 친구가 될 수 없다.

실행 과정은 2번 조건인 원수의 원수를 친구로 먼저 처리해놓고, 1번 조건만 본다.

import java.util.*;
import java.io.*;

public class Boj1765 {
	static LinkedList<Integer> relation[][];
	static boolean visited[];
	
	public static void dfs(int n) {
		for(int friend: relation[1][n]) {
			if(visited[friend]) {continue;}
			visited[friend] = true;
			dfs(friend);
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int N = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		relation = new LinkedList[2][N+1];
		visited = new boolean[N+1];
		
		for(int i=1; i<=N; i++) {
			relation[0][i] = new LinkedList<>();
			relation[1][i] = new LinkedList<>();
		}
		
		for(int i=0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int r = st.nextToken().charAt(0)-'E';
			int n1 = Integer.parseInt(st.nextToken());
			int n2 = Integer.parseInt(st.nextToken());
			relation[r][n1].offer(n2);
			relation[r][n2].offer(n1);
		}
		
		//원수의 원수 => 원수 = 0
		for(int i=1; i<=N; i++) {
			for(int j=0; j<relation[0][i].size(); j++) {
				int enemy = relation[0][i].get(j);//i의 원수
				for(int k=0; k<relation[0][enemy].size(); k++) {
					int f = relation[0][enemy].get(k);//i의 원수의 원수 = 친구
					if(i<f) {
						relation[1][i].add(f);
					}
				}
			}
		}
        
		//dfs
		int result = 0;
		for(int i=1; i<=N; i++) {
			if(visited[i]) {continue;}
			visited[i] = true;
			dfs(i);
			result++;
		}
		System.out.println(result);
	}
}