알고리즘 문제/BOJ

2617번 구슬 찾기

parkit 2019. 1. 18. 03:31
728x90
반응형

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



쉬운 DFS 유형 문제이다.


예제 1을 방향 그래프 2개(무거운지, 가벼운지)를 그려서, 생각해보니 구현 방법이 떠올랐다.


사실상 같은 정답 코드 2개를 첨부한다.








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
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
vector<int> h[100], l[100];
 
int N = 0, M = 0;
 
bool visit[100] = { false, };
 
int cnt = 0;
 
void lDFS(int start)
{
    visit[start] = true;
 
    for (auto i : l[start])
    {
        if (!visit[i])
        {
            ++cnt;
 
            lDFS(i);
        }
    }
}
 
void hDFS(int start)
{
    visit[start] = true;
 
    for (auto i : h[start])
    {
        if (!visit[i])
        {
            ++cnt;
 
            hDFS(i);
        }
    }
}
 
int main(void)
{
    int s = 0, e = 0, result = 0;
 
    scanf("%d %d", &N, &M);
 
    while (M--)
    {
        scanf("%d %d", &s, &e);
 
        l[s].push_back(e); // s보다 가벼운 것들을 push_back
        h[e].push_back(s); // e보다 무거운 것들을 push_back
    }
 
    for (int i = 1; i <= N; i++)
    {
        memset(visit, false, sizeof(visit));
        cnt = 0;
 
        hDFS(i);
 
        if (cnt >= (N + 1) / 2)
        {
            ++result;
            continue;
        }
 
        memset(visit, false, sizeof(visit));
        cnt = 0;
 
        lDFS(i);
 
        if (cnt >= (N + 1) / 2) ++result;
    }
 
    printf("%d\n", result);
 
    return 0;
}
cs














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
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
vector<int> h[100], l[100];
 
int N = 0, M = 0;
 
bool visit[100] = { false, };
 
int lDFS(int start)
{
    visit[start] = true;
 
    int ret = 0;
 
    for (auto i : l[start]) if (!visit[i]) ++ret += lDFS(i);
    
    return ret;
}
 
int hDFS(int start)
{
    visit[start] = true;
 
    int ret = 0;
 
    for (auto i : h[start]) if (!visit[i]) ++ret += hDFS(i);
    
    return ret;
}
 
int main(void)
{
    int s = 0, e = 0, result = 0;
 
    scanf("%d %d", &N, &M);
 
    while (M--)
    {
        scanf("%d %d", &s, &e);
 
        l[s].push_back(e);
        h[e].push_back(s);
    }
 
    for (int i = 1; i <= N; i++)
    {
        memset(visit, false, sizeof(visit));
 
        if (hDFS(i) >= (N + 1) / 2)
        {
            ++result;
            continue; // 어차피 여기서 조건에 맞다면, 아래는 안 봐도 된다.
        }
 
        memset(visit, false, sizeof(visit));
 
        if (lDFS(i) >= (N + 1) / 2) ++result;
    }
 
    printf("%d\n", result);
 
    return 0;
}
cs



728x90
반응형
저작자표시 (새창열림)