백준 1943 거짓말

작성일 | In |

Problem : 거짓말

유형 : 그래프

문제 해석

  • 거짓말을 들키지 않고, 최대한 할 수 있는 파티의 수를 구하라.

문제 재해석

  • 진실을 아는 자가 속해 있는 파티에는 거짓말을 할 수 없다.
  • 진실을 아는 자와 같은 파티에 속했던 사람이 있는 파티에는 거짓말을 할 수 없다.

해결 전략

사람들 간의 연결 그래프

  • 파티 참석자들끼리 다 연결해둔다.
  • DFS 를 통해, 진실을 아는 사람들을 시작으로 순회 해 나간다.

파티, 사람 간의 연결 그래프

  • 사람이 어디 파티에 속해 있는지, 파티에서는 어느 사람이 속해 있는지를 기록한다.
  • 진실된 사람이 속해있는 파티의, 모든 사람들을 기준으로 DFS를 진행한다.

설계, 구현

  • 인접 리스트를 이용하여 관계를 설정하고 DFS를 통해 그래프를 순회 시켰다.

주의할 점

  • 관계를 곰곰히 생각해 볼 것

코드

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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#if 00

#include <bits/stdc++.h>
using namespace std;

vector<int> node[52], party[52], truth_mans;
bool visit[52];
bool visit_check[52][52];

int n, m, k;

bool IsLie(int party_n) {
    for (const auto& man : party[party_n]) {
        if (visit[man]) return false;
    }
    return true;
}

void Dfs(int cur_man) {
    for (const auto &nxt_man : node[cur_man]) {
        if (visit[nxt_man]) continue;
        visit[nxt_man] = true;
        Dfs(nxt_man);
    }
}

void Truth_spread() {
    for (const auto& man : truth_mans) {
        visit[man] = true;
        Dfs(man);
    }
}

void Make_Relationship(int party_n) {
	for (int i = 0; i < (int)party[party_n].size(); ++i) {
		for (int ii = i + 1; ii < (int)party[party_n].size(); ++ii) {
            int a = party[party_n][i];
            int b = party[party_n][ii];

            if (visit_check[a][b]) continue;
            visit_check[a][b] = true;
            visit_check[b][a] = true;
            node[a].push_back(b);
            node[b].push_back(a);
		}
    }
}

void Solve() {
    for (int i = 0; i < m; ++i) {
        Make_Relationship(i);
    }
    Truth_spread();

    int answer = 0;
    for (int i = 0; i < m; ++i) {
        if (IsLie(i)) answer++;
    }
    cout << answer << "\n";
}

void Input() {
    cin >> n >> m;
    cin >> k;

    truth_mans.resize(k);
    for (auto& man : truth_mans) {
        cin >> man;
    }

    int party_mans;
    for (int i = 0; i < m; ++i) {
        cin >> party_mans;
        party[i].resize(party_mans);
        for (auto& man : party[i]) {
            cin >> man;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

#else


#include <bits/stdc++.h>
using namespace std;

vector<int> node[52], party[52], truth_mans;
bool visit[52];

int n, m, k;

bool IsLie(int party_n) {
    for (const auto& man : party[party_n]) {
        if (visit[man]) return false;
    }
    return true;
}

void Dfs(int cur_man) {
    for (const auto &include_party : node[cur_man]) {
        for (const auto& nxt_man : party[include_party]) {
            if (visit[nxt_man]) continue;
            visit[nxt_man] = true;
            Dfs(nxt_man);
        }
    }
}

void Truth_spread() {
    for (const auto& man : truth_mans) {
        visit[man] = true;
        Dfs(man);
    }
}

void Solve() {
    Truth_spread();

    int answer = 0;
    for (int i = 0; i < m; ++i) {
        if (IsLie(i)) answer++;
    }
    cout << answer << "\n";
}

void Input() {
    cin >> n >> m;
    cin >> k;

    truth_mans.resize(k);
    for (auto& man : truth_mans) {
        cin >> man;
    }

    int party_mans;
    for (int party_n = 0; party_n < m; ++party_n) {
        cin >> party_mans;

        int man;
        while(party_mans--) {
            cin >> man;
            party[party_n].push_back(man);
            node[man].push_back(party_n);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    Input();
    Solve();

    return 0;
}

#endif

피드백

  • 첫번째 풀이가 코드 라인이 다른 사람들에 비해 너무 길어 축약 할 수 없을까 고민하였다.
  • 연결 관계를 만들 때, 꼭 사람과 사람간의 관계가 아닌, 사람과 그룹간의 관계로 해도 된다는 것을 깨달았다.
  • 그룹을 이용한다면 union find로도 풀이가 가능해 보인다.
  • 찾아보니 DP , Bitmarking 으로도 풀 수 있다고 한다.