[자바] 백준 12893 - 적의 적 (java)

목차

문제 : boj12893

 

 

필요 알고리즘

• 이분 그래프, 그래프 탐색(BFS, DFS 등)
  
  • 이분 그래프가 만들어지는지 파악할수만 있으면 풀 수 있다. 일반적으로 이분 그래프 판정을 위해 DFS나 BFS를 사용한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  생각과정은 다음과 같다.

 

1. 적의 적은 친구라고 계속해서 연결해나갈 때, 결국 어느 누구의 관점에서 보든 서로 연관이 있는(간선이 연결되어진) N명이 정확히 적과 친구로 나눠질 수 있다면 1을 출력하면 되고, 부적합한 경우가 있다면(2번 입장에서 친구이자 적인 사람이 존재한다거나) 0을 출력하면 된다.

 

2. 즉, 각 친구를 정점으로 치고 적대관계를 간선으로 본 그래프라 생각했을 때, 이분 그래프가 만들어질 수 있다면 1을 출력하고 그렇지 않다면 0을 출력하면 된다.

 

3. 이분 그래프가 어떤건지 모른다면 '이분 그래프 (bipartite graph)' 글을 참고해보자.

 

4. 구현은 dfs로 진행했다. 그냥 매번 번갈아서 번호를 매칭하다가 번호가 어긋나는 지점이 있는지 찾으면 된다!

if (!makeBipartite(i, 0)) {	// 하나라도 false가 떴다면 (번호가 어긋났다면)
    System.out.println(0);	// 0을 출력하고
    return;	// 종료
}

...

if (bipartite[idx] != -1) {	// 이미 번호가 지정됬는데
    return bipartite[idx] == bipartiteNum;	// 번호가 어긋났다면 false 리턴
}

 

 

코드 : github

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int[] bipartite;
    List<Integer>[] edges;
    int n;


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

    private void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

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

        while (m-->0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edges[a].add(b);
            edges[b].add(a);
        }

        bipartite = new int[n+1];
        Arrays.fill(bipartite, -1);

        for (int i = 1; i <= n; i++) {
            if (bipartite[i] != -1) continue;

            if (!makeBipartite(i, 0)) {
                System.out.println(0);
                return;
            }
        }

        System.out.println(1);
    }

    private boolean makeBipartite(final int idx, final int bipartiteNum) {
        if (bipartite[idx] != -1) {
            return bipartite[idx] == bipartiteNum;
        }

        bipartite[idx] = bipartiteNum;
        for (Integer next : edges[idx]) {
            if (!makeBipartite(next, 1-bipartiteNum))
                return false;
        }

        return true;
    }
}