[자바] 백준 3683 - 고양이와 개 (java)

 문제 : boj3683

---

 

필요 알고리즘 개념

• 이분 매칭
  
  • 이분 매칭으로 풀 수 있긴 한데, 아이디어 떠올리기가 좀 많이 어려운 편인거같다.

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

 

---

 

풀이

  아이디어 생각하기도 어려웠고, 이분 매칭으로 처리하려고 해도 모델링이 상당히 어려운 문제였다 ㅠ.

이분 매칭에서 좌측에 고양이를 좋아하는 사람, 우측에 개를 좋아하는 사람을 둔다. 그리고 좌측에서 우측으로 고양이를 좋아하는 사람이 싫어하는 개를 좋아하는 사람과 양방향 간선을 연결한다. 마찬가지로 우측에서 좌측으로, 우측에 있는 개를 좋아하는 사람이 싫어하는 고양이를 좋아하는 좌측의 사람과 양방향 간선을 연결한다. 즉 자기가 싫어하는걸 좋아하는 사람끼리 간선을 연결한다.

 

  그럼 이게 무슨 의미냐면, 서로 공존(?)할 수 없는 사람끼리 연결한 것이다. 그렇다면 남길 수 있는 시청자의 최대값은, 총 시청자의 수에서 서로 공존할 수 없는 사람을 최대한 제거한 경우가 된다. 즉, 'v - 공존할 수 없는 사람들의 최대 매칭 수'가 답이 된다.

 

---

 

코드 : github

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

class Viewer {
    boolean isDogLover;
    int c, d;
    ArrayList<Integer> edge;
    public Viewer(String str) {
        edge = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(str, " CD");
        isDogLover = str.charAt(0) == 'D';
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        c = isDogLover?b:a;
        d = isDogLover?a:b;
    }
}

public class Main {
    int[] matched;
    boolean[] visit;
    ArrayList<Viewer> left, right;

    private boolean matching(int cat) {
        Viewer tmp = left.get(cat);
        for (int dog : tmp.edge) {
            if (visit[dog]) continue;
            visit[dog] = true;
            if (matched[dog] == -1 || matching(matched[dog])) {
                matched[dog] = cat;
                return true;
            }
        }
        return false;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (tc-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int c = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            left = new ArrayList<>(c+1);
            right = new ArrayList<>(d+1);
            for (int i = 0; i < v; i++) {
                Viewer tmp = new Viewer(br.readLine());
                if (tmp.isDogLover) right.add(tmp);
                else left.add(tmp);
            }
            for (int i = 0; i < left.size(); i++) {
                Viewer a = left.get(i);
                for (int j = 0; j < right.size(); j++) {
                    Viewer b = right.get(j);
                    if (a.d == b.d || a.c == b.c) {
                        a.edge.add(j);
                        b.edge.add(i);
                    }
                }
            }

            matched = new int[right.size()];
            Arrays.fill(matched, -1);
            visit = new boolean[right.size()];
            int cnt = 0;
            for (int i = 0; i < left.size(); i++) {
                if (matching(i)) {
                    cnt++;
                    visit = new boolean[right.size()];
                }
            }
            sb.append(v-cnt).append('\n');
        }
        System.out.print(sb);
    }

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