[BOJ 1765] 닭싸움 팀 정하기 (Java)

BOJ 1765 닭싸움 팀 정하기

문제풀이

이 문제는 다음의 두 조건이 핵심인데 그 중에서도 두 번째 조건이 중요하다.

• 내 친구의 친구는 내 친구이다.
• 내 원수의 원수도 내 친구이다.

그래프 상에서 type이 F인 간선으로 연결되어 있으면 친구다. 따라서 첫 번째 조건인 친구의 친구는 따로 간선을 추가하지 않아도 이미 연결되어있다. 하지만 두 번째 조건의 원수의 원수는 친구이므로 새로운 간선을 추가해야한다.

• 이미 존재하는 간선정보를 바탕으로 1 ~ N의 정점에서 시작하여 원수의 원수인 정점과 친구 간선을 연결한다.
• 1 ~ N의 정점에서 출발하여 친구 간선으로 연결된 모든 정점을 방문하며 친구 그룹의 수를 세어본다.

구현코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static class Edge {
		int from, to, type;
		
		Edge(int to, int type){
			this.to = to;
			this.type = type;
		}
		
		@Override
		public String toString() {
			return "[" + to + ", " + type + "]";
		}
	}

	static Queue<Edge> q;
	static ArrayList<Edge>[] adj;
	static boolean[] visited;
	static int N, M, ans;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		q = new LinkedList<>();
		adj = new ArrayList[N + 1];
		visited = new boolean[N + 1];
		ans = 0;
		
		for(int i = 1 ; i <= N ; ++i) adj[i] = new ArrayList<>();
		
		for(int i = 0 ; i < M ; ++i) {
			st = new StringTokenizer(br.readLine());
			
			String type = st.nextToken();
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			
			if(type.equals("E")) {
				adj[from].add(new Edge(to, 0));
				adj[to].add(new Edge(from, 0));
			} else {
				adj[from].add(new Edge(to, 1));
				adj[to].add(new Edge(from, 1));
			}
		}
		
		for(int i = 1 ; i <= N ; ++i) {
			visited[i] = true;
			
			for(Edge e : adj[i]) {
				q.offer(e);
				visited[e.to] = true;
			}
			
			findFriend(i);
			visited = new boolean[N + 1];
			q.clear();
		}
		
		for(int i = 1 ; i <= N ; ++i) {
			if(visited[i]) continue;
			visited[i] = true;
			
			for(Edge e : adj[i]) {
				if(e.type == 1) {
					q.offer(e);
					visited[e.to] = true;
				}
			}
			
			makeTeam();
		}
		
		System.out.println(ans);
	}

	private static void makeTeam() {
		ans++;
		
		while(!q.isEmpty()) {
			Edge e = q.poll();
			
			if(e.type == 0) continue;
			
			for(Edge ne : adj[e.to]) {
				if(visited[ne.to]) continue;
				
				if(ne.type == 1) {
					q.offer(ne);
					visited[ne.to] = true;
				}
			}
		}
	}

	private static void findFriend(int start) {
		ArrayList<Edge> temp = new ArrayList<>();
		
		while(!q.isEmpty()) {
			temp.clear();
			
			Edge e = q.poll();
			
			for(Edge ne : adj[e.to]) {
				if(visited[ne.to]) continue;
				
				if(e.type == 0 && ne.type == 0) {
					temp.add(ne);
					visited[ne.to] = true;
				}
			}
			
			for(Edge ne : temp) {
				adj[start].add(new Edge(ne.to, 1));
				adj[ne.to].add(new Edge(start, 1));
			}
		}
	}
	
}