[백준 23818 JAVA] 원수의 원수

 

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

class Main {
    static int N, M, K;
    static ArrayList<Term>[] graph;
    static int[] group;
    static int[] relate;
    static boolean[] isError;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        graph = new ArrayList[N + 1];
        group = new int[N + 1];
        relate = new int[N + 1];
        isError = new boolean[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a].add(new Term(b, t));
            graph[b].add(new Term(a, t));
        }
        int groupIdx = 0;
        for (int i = 1; i <= N; i++) {
            if (group[i] != 0) continue;
            groupIdx++;
            group[i] = groupIdx;
            dfs(i, 0, groupIdx);
        }
        //그룹 확인
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if (group[a] != group[b]) {
                System.out.println("Unknown");

            }
            if (group[a] == group[b]) {
                if (isError[group[b]]) {
                    System.out.println("Error");
                    continue;
                }
                if (relate[a] == relate[b]) {
                    System.out.println("Friend");
                } else {
                    System.out.println("Enemy");
                }

            }
        }

    }

    static void dfs(int node, int prev, int groupIdx) {
        for (int i = 0; i < graph[node].size(); i++) {
            int next = graph[node].get(i).friend;
            int relation = graph[node].get(i).relation;
            if (next == prev) continue;
            if (group[next] != 0) {
                if ((relation == 0 && relate[node] != relate[next]) ||
                        (relation == 1 && relate[node] == relate[next])) {
                    isError[groupIdx] = true;
                }
            } else {
                group[next] = groupIdx;
                if (relation == 0) {
                    relate[next] = relate[node];
                }
                if (relation == 1) {
                    relate[next] = 1 - relate[node];
                }
                dfs(next, node, groupIdx);
            }
        }
    }
}

class Term {
    int friend, relation;//0: 친구 1:적

    public Term(int friend, int relation) {
        this.friend = friend;
        this.relation = relation;
    }
}

코드 참고 https://burningfalls.github.io/algorithm/boj-23818/

[BOJ 23818] 백준 23818번 - 원수의 원수