Algorithm/BOJ

소가 길을 건너간 이유 6 - 14466

jhg0406 2020. 4. 1. 16:59
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
//14466 - 소가 길을 건너간 이유 6
 
#include <iostream>
#include <vector>
using namespace std;
 
int N, K, R;
int arr[100][100];
vector<vector<int>> adj;
bool isCow[10000];
int xarr[2] = {1, 0};
int yarr[2] = {0, 1};
vector<int> bucket;
bool visit[10000];
int count, ans;
 
int ch(int x1, int y1, int x2, int y2)
{
    if(y1 + 1 == y2) return 1;
    else if(x1 + 1 == x2) return 2;
    else return 0;
}
 
void init()
{
    cin >> N >> K >> R;
    ans = 0;
    bucket = vector<int>();
    adj = vector<vector<int>>(N*N);
    int x1, y1, x2, y2;
    for (int i = 0; i < R; ++i)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        --x1, --y1, --x2, --y2;
        if(x1 > x2 || y1 > y2) swap(x1, x2) , swap(y1, y2);
        arr[x1][y1] += ch(x1, y1, x2, y2);
    }
 
    for(int x = 0; x<N; ++x)
        for(int y = 0; y<N; ++y)
        {
            int here = x*N+y;
            int right = x*N+y+1;
            int down = (x+1)*N+y;
            if(y+1 == N) right = here;
            if(x+1 == N) down = here;
            if(!arr[x][y] || arr[x][y] == 1)
            {
                adj[here].push_back(down);
                adj[down].push_back(here);
            }
            if(!arr[x][y] || arr[x][y] == 2)
            {
                adj[here].push_back(right);
                adj[right].push_back(here);
            }
        }
    
    for(int i = 0; i<K; ++i)
    {
        cin >> x1 >> y1;
        --x1, --y1;
        isCow[x1*N+y1] = true;
    }
}
 
void dfs(int here)
{
    visit[here] = true;
    if(isCow[here]) ++count;
    for(int i = 0; i<adj[here].size(); ++i)
    {
        int there = adj[here][i];
        if(!visit[there])
            dfs(there);
    }
}
 
int main()
{
    init();
    for(int i = 0; i<N*N; ++i)
        if(!visit[i])
        {
            count = 0;
            dfs(i);
            bucket.push_back(count);
        }
 
    for(int i = 0; i<bucket.size(); ++i)
        for(int j = i+1; j<bucket.size(); ++j)
            ans += bucket[i]*bucket[j];
    cout << ans;
}
 cs

 

 

 

 

 

 

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

 

14466번: 소가 길을 건너간 이유 6

문제 소가 길을 건너간 이유는 그냥 길이 많아서이다. 존의 농장에는 길이 너무 많아서, 길을 건너지 않고서는 별로 돌아다닐 수가 없다. 존의 농장에 대대적인 개편이 있었다. 이제 작은 정사각형 목초지가 N×N (2 ≤ N ≤ 100) 격자로 이루어져 있다. 인접한 목초지 사이는 일반적으로 자유롭게 건너갈 수 있지만, 그 중 일부는 길을 건너야 한다. 농장의 바깥에는 높은 울타리가 있어서 소가 농장 밖으로 나갈 일은 없다. K마리의 (1 ≤ K ≤ 100,

www.acmicpc.net

 

 

 

 

 

 

소가 길을 건너간 이유 6

그래프로 모델링 한 후 dfs를 이용해 길을 건너지 않고 만날수 있는 소들의 마리수를 셌습니다.