[JAVA] BOJ 백준 1765번 - 닭싸움 팀 정하기

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

일단 입력값은 연결리스트를 이용해 friend 관계와 enemy 관계를 나눠서 입력받았다.

friend = new ArrayList[n+1];
enemy = new ArrayList[n+1];

for (int i = 1; i <= n; i++) {
    friend[i] = new ArrayList<>();
}
for (int i = 1; i <= n; i++) {
    enemy[i] = new ArrayList<>();
}

for (int i = 0; i < m; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    char conn = st.nextToken().charAt(0);
    int a = Integer.parseInt(st.nextToken());
    int b = Integer.parseInt(st.nextToken());

    if (conn == 'E') {
        enemy[a].add(b);
        enemy[b].add(a);
    }
    else {
        friend[a].add(b);
        friend[b].add(a);
    }
}

 

그 후 DFS 알고리즘을 이용해 같은 팀인 사람들을 먼저 찾는다고 생각했고, 그 다음엔 원수의 원수를 depth를 0부터 시작해 짝수일 경우에 같은 팀으로 판단하여 거기서 또 친구들을 연결해 주는 방식으로 코드를 작성했다.

 

dfs 함수에서 friendDFS 함수를 먼저 호출하는데, 친구인 사람들을 먼저 같은 팀으로 설정해주는 함수이다.

다음으로 enemyDFS 함수가 호출되는데, depth를 기준으로 원수의 원수일 경우(= depth가 짝수), 같은 팀이므로 거기서 또 친구인 사람들을 같은 팀으로 넣어주어 friendDFS을 호출한다.

public static void dfs (int idx, int teamNumber) {
    friendDFS(idx, teamNumber);
    enemyDFS(new boolean[n+1], idx, 0, teamNumber);
}

public static void enemyDFS (boolean[] check, int idx, int depth, int teamNumber) {
    check[idx] = true;
    if (depth % 2 == 0) {
        friendDFS(idx, teamNumber);
    }

    for (Integer i: enemy[idx]) {
        if (!check[i]) {
            enemyDFS(check, i, depth + 1, teamNumber);
        }
    }
}

public static void friendDFS (int idx, int teamNumber) {
    team[idx] = teamNumber;

    for (Integer i : friend[idx]) {
        if (team[i] == 0) {
            friendDFS(i, teamNumber);
        }
    }
}

---

3. 자바 코드

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

class Main {
    static int n;
    static int[] team;
    static int teamMax;
    static List<Integer>[] friend;
    static List<Integer>[] enemy;

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        friend = new ArrayList[n+1];
        enemy = new ArrayList[n+1];

        for (int i = 1; i <= n; i++) {
            friend[i] = new ArrayList<>();
        }
        for (int i = 1; i <= n; i++) {
            enemy[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            char conn = st.nextToken().charAt(0);
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if (conn == 'E') {
                enemy[a].add(b);
                enemy[b].add(a);
            }
            else {
                friend[a].add(b);
                friend[b].add(a);
            }
        }

        team = new int[n+1];

        for (int i = 1; i <= n; i++) {
            if (team[i] == 0) {
                dfs(i, ++teamMax);
            }
        }

        bw.write(teamMax+"");

        br.close();
        bw.flush();
        bw.close();
    }

    public static void dfs (int idx, int teamNumber) {
        friendDFS(idx, teamNumber);
        enemyDFS(new boolean[n+1], idx, 0, teamNumber);
    }

    public static void enemyDFS (boolean[] check, int idx, int depth, int teamNumber) {
        check[idx] = true;
        if (depth % 2 == 0) {
            friendDFS(idx, teamNumber);
        }

        for (Integer i: enemy[idx]) {
            if (!check[i]) {
                enemyDFS(check, i, depth + 1, teamNumber);
            }
        }
    }

    public static void friendDFS (int idx, int teamNumber) {
        team[idx] = teamNumber;

        for (Integer i : friend[idx]) {
            if (team[i] == 0) {
                friendDFS(i, teamNumber);
            }
        }
    }
}

---

4. 결과 및 회고

조금 더 빠르게 풀어보자.