반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. 최소 버텍스 커버 :: http://www.crocus.co.kr/756

2. 이분 매칭


이 문제를 최소 버텍스 커버로 생각해본다면 다음 문제와 같게 생각해볼 수 있다.

[2414번] 게시판 구멍 막기 :: http://www.crocus.co.kr/750


이제 최소 버텍스 커버 문제임을 이해했다면


x와 y에 대한 이분 매칭 문제로 변환 시킬 수 있고, 이분 매칭으로 나온 return값은 최소 몇개의 버텍스가 필요한지 알려주는 역할을 한다.


따라서 3이하로 답이 나온다면 1, 그게 아니라면 0으로 정답을 출력한다.


이때 n의 범위는 5만이고 값의 범위는 10억이니 좌표 압축을 통해 이분 매칭이 가능하게 만들어주자.




소스 코드 : 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
#include <memory.h>
 
using namespace std;
 
typedef pair<int, int > pii;
 
pii arr[50002];
 
int visit[50002];
int visitCnt;
 
int aMatch[50002];
int bMatch[50002];
vector<int> vc[50002];
int xNum;
 
bool comp(const pii &a, const pii &b)
{
    return a.second < b.second;
}
 
bool dfs(int a)
{
    if (visit[a] == visitCnt)
        return false;
 
    visit[a] = visitCnt;
 
    for (int i = 0; i < vc[a].size(); i++)
    {
        int b = vc[a][i];
 
        if (bMatch[b] == -1 || dfs(bMatch[b]))
        {
            bMatch[b] = a;
            aMatch[a] = b;
 
            return true;
        }
    }
    return false;
}
 
int bipartiteMatch()
{
    memset(aMatch, -1, sizeof(aMatch));
    memset(bMatch, -1, sizeof(bMatch));
 
    int ans = 0;
 
    for (int start = 0; start <= xNum; start++)
    {
        visitCnt++;
        ans += dfs(start);
    }
 
    return ans;
}
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d %d", &arr[i].first, &arr[i].second);        
 
    sort(arr, arr + n);
 
    // x 좌표 압축
    int num = 0;
    for (int i = 0; i < n; i++)
    {
        if (i + 1 < n && arr[i].first != arr[i + 1].first)
        {
            arr[i].first = num;
            num++;
        }
        else
            arr[i].first = num;
    }
    
    // 이분 매칭을 위한 값
    xNum = num;
 
    // y 좌표 압축
    num = 0;
    sort(arr, arr + n, comp);
    for (int i = 0; i < n; i++)
    {
        if (i + 1 < n && arr[i].second != arr[i + 1].second)
        {
            arr[i].second = num;
            num++;
        }
        else
            arr[i].second = num;
    }
 
    sort(arr, arr + n);
    
    for (int i = 0; i < n; i++)
    {
        int a = arr[i].first;
        int b = arr[i].second;
 
        vc[a].push_back(b);
    }
 
    int ans = bipartiteMatch();
 
    if (ans <= 3)
        printf("1");
    else
        printf("0");
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형
저작자표시 비영리 변경금지

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[14626번] ISBN  (0) 2017.11.30
[14625번] 냉동식품  (2) 2017.11.30
[1062번] 가르침  (3) 2017.11.28
[2533번] 사회망 서비스(SNS)  (2) 2017.11.24
[3613번] Java vs C++  (0) 2017.11.24

티스토리툴바