[백준] 23818번 - 원수의 원수 (Java)

문제

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

23818번: 원수의 원수

---

알고리즘

이분 그래프, 깊이 우선 탐색(DFS)

 

모든 관계를 저장해두고, DFS로 타고타고 들어가면 된다. DFS로 타고 들어가면서 answer 배열에 관계를 저장해둔다. 이때, 동일한 그래프 내 있는 노드들의 answer 절대값은 동일하다.

 

예를 들어, 1 - 3 - 2 그래프와 4 - 5 그래프가 있다면 전자의 그래프의 answer 절댓값은 1, 후자 그래프의 answer 절댓값은 2 이런식으로 dfs에 새로 들어갈 때마다 idx를 증가시켜 같은 그래프로 이어져 있다는 것을 표시한다.

 

DFS로 관계를 하나하나 타고 들어가면서, 현재 노드와 다음 노드 사이의 관계가 적대 관계라면 answer에 부호가 반대인 idx값을, 친구 관계라면 동일한 idx를 저장한다. 예시로 1 -> 3  ->2 순서대로 탐색하고 1 - 3이 적대 관계이고 3 - 2 가 친구 관계이며, idx가 1이라고 한다면, answer[1] = 1, answer[3] = - 1, answer[2] = -1 처럼 저장된다. 그리고 마지막에 출력할 때 이 answer 배열만 봐서 a와 b의 answer 값이 반대라면 "Enemy", 동일하다면 "Friend", 절대값이 아예 다르다면 "Unknown"을 출력하면 된다.

 

마지막으로 "Error"의 경우를 처리하기 위해서 error 배열을 하나 만든다. DFS 탐색과정 중, 이미 방문했던 노드를 또 방문하는데, 관계가 이상하다면 해당 간선은 오염됐다는 것을 표시하기 위해서 error[idx] = true로 만들어준다. 그리고 출력할 때, 적대/친구를 표시하기 전에 error가 true면 대신 "Error"를 표시하면 쉽게 풀린다.

---

코드

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

class Relationship {
    int connect;
    int relation;

    public Relationship(int connect, int relation) {
        this.connect = connect;
        this.relation = relation;
    }
}

public class Main {
    static ArrayList<Relationship>[] relation;
    static boolean[] visited;
    static boolean[] error;
    static int[] answer;
    static int idx = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        relation = new ArrayList[n + 1];
        visited = new boolean[n + 1];
        answer = new int[n + 1];
        error = new boolean[n + 1];

        for (int i = 1; i < relation.length; i++) {
            relation[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());

            relation[a].add(new Relationship(b, t));
            relation[b].add(new Relationship(a, t));
        }

        for (int i = 1; i < n + 1; i++) {
            if (!visited[i]) {
                idx++;
                answer[i] = idx;
                dfs(i);
            }
        }

        StringBuilder sb = new StringBuilder();
        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 (Math.abs(answer[a]) != Math.abs(answer[b])) sb.append("Unknown\n");
            else if (error[Math.abs(answer[a])]) sb.append("Error\n");
            else if (answer[a] == answer[b]) sb.append("Friend\n");
            else if (answer[a] == -answer[b]) sb.append("Enemy\n");
        }

        System.out.println(sb);
    }

    public static void dfs(int cur) {
        for (Relationship now : relation[cur]) {
            int nxt = now.connect;
            int relation = now.relation;
            if (!visited[nxt]) {
                visited[nxt] = true;
                if (relation == 0) answer[nxt] = answer[cur];
                else answer[nxt] = -answer[cur];
                dfs(nxt);
            } else {
                if ((relation == 0 && answer[nxt] == -answer[cur]) || (relation == 1 && answer[nxt] == answer[cur])) {
                    error[idx] = true;
                }
            }
        }
    }
}