[Java] 백준 1765번 닭싸움 팀 정하기 문제 952hi의 접근방법

 

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

1765번: 닭싸움 팀 정하기

---

 

1. 문제접근

내 친구는 친구다 , 원수의 원수는 친구다 라는 표현을 보고 그룹을 나눈다라는 느낌을 받았고

서로소개념인 유니온 파인드 개념을 사용해야겠다고 생각이 들었다.

 

입력받을때 친구는 바로 유니온 해주고 각 인덱스별 원수가 2명이상있다는것은 그룹으로 처리해줘야 한다는 말이기때문에 원수의 수를 세주고 2이상이면 그 원수를 유니온 해주는 방식으로 풀었다.

 

위 그림은 예제 입력 1을 바탕으로 배열을 표현한 것 입니다.

각 원소가 뜻하는 바는 0은 관계없음, 1은 친구, -1은 원수 입니다.

친구와 1은 입력받으면서 처리를 해줘서 크게 의미는 지니지 않습니다.

 

원수일 경우 하나의 행을 볼때 2이상이라는 것은 그 원수들은 모두 친구가 되어야합니다.

빨간색으로 표시된 부분은 1번 사람이 2번과 4번 사람과 원수관계이기에 친구가 되어야 하는 부분은

파란색으로 표시된 1번 열에 모두 표시되어 있습니다. 

그래서 1번 열에 -1로 표시된 사람을 그룹에 합쳐주고 -1값을 0으로 변경해줍니다.

변경해주지않고 다음행으로 넘어가게 된다면 중복처리가 되어 시간적인 낭비가 생깁니다.

 

2. 느낀점

 

가끔 백준 난이도 시스템이 알면 맞고 모르면 틀리는 문제에 난이도를 높게 주는 느낌을 받았다

크게 어렵지는 않았다

 

3. 코드

 

import java.io.*;
import java.util.*;
public class boj1765 {
	static int parent[],n,map[][];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz;
		
		n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		map = new int[n+1][n+1];
		int res[] = new int[n+1];
		parent = new int[n+1];
		for(int i=1;i<n+1;i++) parent[i] = i; // 부모배열 초기화
		
		int s,e;
		String type;
		for(int i=0;i<m;i++) {
			stz = new StringTokenizer(br.readLine());
			type = stz.nextToken();
			s = Integer.parseInt(stz.nextToken());
			e = Integer.parseInt(stz.nextToken());
			if(type.equals("F")) {
				map[s][e] = 1;
				map[e][s] = 1;
				uparent(s, e);// 친구라면 그룹합치기
			}else {
				map[s][e] = -1;
				map[e][s] = -1;
			}
		}
		for(int i=0;i<n;i++) {
			int cnt =0;
			int idx =0;
			for(int j=0;j<n;j++) {
				if(map[i][j]==-1) {
					idx = j;
					cnt++;
				}
			}
			if(cnt >=2) { // 원수가 2명이상이면 원수의 원수는 친구이므로 친구추가 
				map[i][idx] = 0; // 0으로 바꿔주는이유는 이미 친구간 그룹형성했기에 다른 곳에서 또 다시 합쳐지지 않기위해
				enemy(i,idx);
			}
		}
		for(int i=1;i<n+1;i++) {
			fparent(i); // 부모 제대로 가르치게 하기
			res[parent[i]] ++; // 그룹갯수 확인을 위한 값증가
		}
		int cnt =0;
		for(int i=1;i<n+1;i++) {
			if(res[i]!=0) cnt++;
		}
		System.out.println(cnt);
	}

	private static void enemy(int x,int idx) {
		for(int j=0;j<n+1;j++) {
			if(map[x][j]==-1) {
				 if(uparent(idx, j)) map[x][j]=0;
			}
		}
	}
	private static int fparent(int i) {
		if(parent[i]==i) return i;
		return parent[i] = fparent(parent[i]);
	}
	private static boolean uparent(int x,int y) {
		x = fparent(x);
		y = fparent(y);
		if(x==y) return false;
		if(x>y) parent[x] = y; 
		else parent[y] = x;
		return true;
	}
}

 

4. 시간 및 메모리