백준 1765 자바 - 닭싸움 팀 정하기 (BOJ 1765 JAVA)

문제 : boj1765

 

 

1. '내 친구의 친구는 내 친구' + '내 원수의 원수도 내 친구'

  이걸 해석은 명확히 해야한다. 우선 '내 친구의 원수'에 대한 내용은 없으니 신경쓸 필요가 없다. 그리고 '내 친구의 친구는 내 친구' 라고 했으니 내 친구라면 쭉쭉 이어나가면서 친구를 찾을 수 있음을 알 수 있다.

 

  '내 원수의 원수도 내 친구' 부분이 문제인데, 원수의 원수의 원수 이런건 생각할 필요가 없다. 딱 두 단계에 걸친 원수사이면 친구라는 말이다. 또한 첫 번째 조건과 합쳐져서, 원수의 원수의 친구 또한 내 친구이다! 원수의 원수의 친구의 친구 또한 내 친구이다!

 

  좀 헷갈릴 수 있는데 그냥 주어진 조건 2개에 대해 여러 경우를 생각해보면 저렇게 된다. 정리해보면

- 내 원수 -> 그냥 원수임

- 내 원수의 친구 -> 아무 관계 없음

- 내 친구의 원수 -> 아무 관계 없음

- 내 원수의 원수 -> 친구임

- 내 친구 -> 친구임

- 내 친구의 친구 -> 친구임

- 내 친구의 친구의 ...(대충 '친구의'가 많음)... 친구 -> 친구임

- 내 원수의 원수의 친구 -> 친구임

- 내 원수의 원수의 친구의 ...(대충 '친구의'가 많음) 친구 -> 친구임

 

와 같다.

 

 

2. 우선 원수는 빼고 생각해보자.

  내 경우엔 두 부분으로 나눠서 생각했다. 우선 원수의 원수도 내 친구라는 부분이 없다면, 이 문제는 그냥 모든 항목을 완전탐색해서 그룹을 나누면 끝나는 아주 간단한 DFS 문제가 된다. 모순인 경우도 없다고 했으므로 친구만 존재한다면 서로 간선조차 연결 안되있을테니 다음과 같은 그래프 형태일 것이다. 이러한 형태의 그래프에서는 union-find와 같은 disjoint set 알고리즘을 굳이 쓰지 않더라도 방문체크를 하면서 완전탐색 해보면 그룹의 수를 구할 수 있다.

 

3. 그럼 이제 원수의 원수도 생각해보자.

  이 문제에서 만약 모순이 있다면 -1을 출력하라! 이런 조건이었다면 훨씬 더 어려웠을 것이다. 하지만 모순이 있는 입력이 없으므로, 원수의 원수는 그냥 친구로 치면 된다. 그럼 원수만 따로 생각해서 1부터 n번까지 전부 확인하면서 해당 번호의 원수의 원수를 친구 간선에 추가해둔다면, 바로 '2'를 적용할 수 있게 된다.

 

  따라서 마찬가지로 완전탐색(다만 시작 노드로부터 거리가 2인 원수까지만 확인)을 통해 원수 간선을 탐색하며 친구를 모두 찾아두면 된다.

 

 

4. 전체 로직

4.1 입력을 받으면서 친구 간선과 원수 간선을 별도로 저장해둔다. (코드에서 친구간선은 fArr, 원수간선은 eArr)

4.2 1부터 n까지의 노드에서 시작해서 거리 2만큼만 원수간선을 탐색하면서 원수의 원수를 친구간선에 추가한다. (코드의 eDfs() 참고)

4.3 친구간선을 완전탐색하면서 그룹의 수를 구한다. (코드의 dfs() 참고)

 

 

  

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    int n;
    ArrayList<Integer>[] fArr, eArr;
    boolean[] fv, ev;

    private void eDfs(int root, int s, int cnt) {
        if (cnt == 2) {
            fArr[root].add(s);
            return;
        }

        for (Integer next : eArr[s]) {
            if (ev[next]) continue;
            ev[next] = true;
            eDfs(root, next, cnt+1);
        }
    }

    private void dfs(int s) {
        for (Integer next : fArr[s]) {
            if (fv[next]) continue;
            fv[next] = true;
            dfs(next);
        }
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        fArr = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) fArr[i] = new ArrayList<>();
        eArr = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) eArr[i] = new ArrayList<>();

        while (m-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            char c = st.nextToken().charAt(0);
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            switch (c) {
                case 'E' : eArr[a].add(b); eArr[b].add(a); break;
                case 'F' : fArr[a].add(b); fArr[b].add(a); break;
            }
        }

        for (int i = 1; i <= n; i++) {
            ev = new boolean[n+1];
            eDfs(i, i, 0);
        }


        fv = new boolean[n+1];
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (!fv[i]) {
                cnt++;
                dfs(i);
            }
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}