[BOJ-1765][DFS] 닭싸움 팀 정하기 - Java

문제 바로가기

1765번: 닭싸움 팀 정하기

BFS 태그에서 찾았는데 DFS로 풀었씀다..

1. 내 친구의 친구는 내 친구이다.

2. 내 원수의 원수도 내 친구이다.

이 규칙을 잘 생각하고 풀면 됨미다..

friend 그래프와 enemy 그래프를 만들고, N 번을 돌면서 check 배열을 두어 해당 사람을 봐줬는지 체크하면서 봐주면 됩니다..

뭔서린지 모르겠ㄴㅔ

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int n;
    static ArrayList<ArrayList<Integer>> friend = new ArrayList<>();
    static ArrayList<ArrayList<Integer>> enemy = new ArrayList<>();
    static int m;
    static boolean []check;

    public static void dfs(int idx) {
        for (int t : friend.get(idx)) {
            if(check[t] == false) {
                check[t] = true;
                dfs(t);
            }
        }
        for (int t : enemy.get(idx)) {
            for (int e : enemy.get(t)) {
                if(check[e] == false) {
                    check[e] = true;
                    dfs(e);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

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

        for(int i = 0; i< m ;i++){
            char fe = sc.next().charAt(0);
            int from = sc.nextInt();
            int to = sc.nextInt();

            if(fe == 'F'){
                friend.get(from).add(to);
                friend.get(to).add(from);
            }
            else{
                enemy.get(from).add(to);
                enemy.get(to).add(from);
            }
        }

        //check friend or enemy
        int answer = 0;
        for(int i = 1; i<= n; i++){
            if(check[i] == false){
                check[i] = true;
                dfs(i);
                answer++;
            }
        }

        System.out.println(answer);
    }
}

 

friend: 친구관계를 나타내는 그래프입니다. friend[p] = q 라면 p와 q는 친구 사이란 뜻입니다. 방향이 없는 그래프기 때문에 양방향으로 넣어줬는데, 어차피 check로 봐주기 때문에 p가 q보다 작은게 보장이 되면 굳이 양쪽 다 안넣어도 될 것 같습니다. 지금 너무 잠와서 예상만

 

enemy: 원수관계를 나타내는 그래프입니다. 원수의 원수는 나의 친구이기 때문에 별도로 필요합니다.

 

check: i번 사람에 대해 체크했는지를 저장하는 배열입니다. 같은 팀이면 check 해주어서 이미 체크된 팀의 팀원을 따로 안봐주는 겁니다. 왜냐면 나는 false일 때 answer를 ++했기 때문에.

public static void dfs(int idx) {
        for (int t : friend.get(idx)) {
            if(check[t] == false) {
                check[t] = true;
                dfs(t);
            }
        }
        for (int t : enemy.get(idx)) {
            for (int e : enemy.get(t)) {
                if(check[e] == false) {
                    check[e] = true;
                    dfs(e);
                }
            }
        }
    }

check가 false인(한 번도 체크하지 않은 팀원) idx에 한해서 dfs로 같은 팀원들을 탐색하면서 체크해줍니다. dfs를 한 번 수행할 때마다 팀의 수가 ++ 됩니다.

friend에서 쭈루룩 dfs로 봐주고, enemy에서 쭈루룩 봐줍니다. 원수의 원수는 나의 친구임을 기억합시다.

 

 

 

감사합니다.