Notice
Recent Posts
Recent Comments
Link
궤도
[백준] 1043번 : 거짓말 본문
문제
풀이
처음에는 각 사람들의 연결관계를 그래프로 만들어서 dfs했는데 생각해보니
정답을 맞고 보니 유니온 파인드로도 풀 수 있단걸 깨달아서 유니온 파인드로도 풀었다.
두 풀이 모두 중요한 부분은 모든 파티 정보를 고려해서 연결되어 있는 사람들을 전부 찾아야 한다는 것이다.
소스코드 - dfs
#include <iostream>
#include <vector>
using namespace std;
vector<bool> isLie; //이 사람에게 거짓말을 할 수 있나?
vector<vector<int>> party_info; //파티 정보
vector<vector<int>> graph; //연결 정보
void dfs(int cur) { //거짓말을 할 수 없는 사람을 체크
isLie[cur] = false;
for (int i = 0; i < graph[cur].size(); i++) {
if (isLie[graph[cur][i]])
dfs(graph[cur][i]);
}
}
int main() { //dfs 풀이
int N, M, t, num, input;
vector<int> init;
cin >> N >> M;
isLie.assign(N + 1, true);
party_info.assign(M, vector<int>(0));
graph.assign(N + 1, vector<int>(0));
cin >> t;
init.assign(t, 0);
for (int i = 0; i < t; i++) //처음에 주어진 진실을 아는 사람
cin >> init[i];
for (int i = 0; i < M; i++) {
cin >> num;
for (int j = 0; j < num; j++) { //파티 정보
cin >> input;
party_info[i].push_back(input);
}
for (int j = 0; j < num - 1; j++) { //그래프에 연결관계 넣기
for (int k = j + 1; k < num; k++) {
graph[party_info[i][j]].push_back(party_info[i][k]);
graph[party_info[i][k]].push_back(party_info[i][j]);
}
}
}
for (int i = 0; i < init.size(); i++) //dfs 돌면서 진실을 말해야 하는 사람 체크
dfs(init[i]);
int cnt = 0;
for (int i = 0; i < M; i++) { //파티 정보의 첫번째 사람만 체크해도 됨
if (isLie[party_info[i][0]])
cnt++;
}
cout << cnt;
}dfs 풀이의 전체 소스코드다.
vector<bool> isLie; //이 사람에게 거짓말을 할 수 있나?
vector<vector<int>> party_info; //파티 정보
vector<vector<int>> graph; //연결 정보먼저 특정 사람에게 거짓말을 할 수 있는지 저장하는 isLie 벡터와
파티의 정보, 그리고 사람간의 연결 정보를 담을 벡터들을 선언한다.
cin >> t;
init.assign(t, 0);
for (int i = 0; i < t; i++) //처음에 주어진 진실을 아는 사람
cin >> init[i];초기 입력으로 주어지는 진실을 아는 사람들의 정보를 init 벡터에 담는다.
이걸 나중에 한번에 dfs 하려고 한다.
for (int i = 0; i < M; i++) {
cin >> num;
for (int j = 0; j < num; j++) { //파티 정보
cin >> input;
party_info[i].push_back(input);
}
for (int j = 0; j < num - 1; j++) { //그래프에 연결관계 넣기
for (int k = j + 1; k < num; k++) {
graph[party_info[i][j]].push_back(party_info[i][k]);
graph[party_info[i][k]].push_back(party_info[i][j]);
}
}
}그리고 파티 정보를 받은 다음, 같은 파티에 있는 모든 두 사람의 쌍에 대해 연결 관계를 넣어준다.
for (int i = 0; i < init.size(); i++) //dfs 돌면서 진실을 말해야 하는 사람 체크
dfs(init[i]);처음에 입력한 init 벡터에 대해 dfs를 돌며 연결된 사람을 전부 찾는데
void dfs(int cur) { //거짓말을 할 수 없는 사람을 체크
isLie[cur] = false;
for (int i = 0; i < graph[cur].size(); i++) {
if (isLie[graph[cur][i]])
dfs(graph[cur][i]);
}
}dfs를 돌면서 당연히 isLie도 false로 체크해야 한다.
int cnt = 0;
for (int i = 0; i < M; i++) { //파티 정보의 첫번째 사람만 체크해도 됨
if (isLie[party_info[i][0]])
cnt++;
}
cout << cnt;마지막으로 각 파티의 첫번째 사람의 isLie만 확인하며 cnt를 증가한다.
각 파티의 모든 사람은 다함께 isLie가 true거나 false일 것이므로 한 명만 체크해도 된다.
소스코드 - 유니온 파인드
#include <iostream>
#include <vector>
using namespace std;
vector<bool> isLie; //이 사람에게 거짓말을 할 수 있나?
vector<int> parent; //부모 정보
vector<vector<int>> party_info; //파티 정보
int findParent(int x) { //parent[x]가 음수가 될 때까지(root에 다다를 때까지) 재귀 함수 호출
if (parent[x] < 0)
return x;
return parent[x] = findParent(parent[x]);
}
int unionInput(int x, int y) { //union 한 뒤, 집합의 크기 리턴
int x_p = findParent(x); //x의 부모
int y_p = findParent(y); //y의 부모
if (x_p == y_p) //이미 같은 집합
return parent[x_p];
if (parent[x_p] < parent[y_p]) { //x_p를 root로 하는 노드가 더 많으면 x_p -> y_p
parent[x_p] += parent[y_p];
parent[y_p] = x_p;
return parent[x_p];
} else { //y_p를 root로 하는 노드가 더 많으면 y_p -> x_p
parent[y_p] += parent[x_p];
parent[x_p] = y_p;
return parent[y_p];
}
}
int main() { //유니온 파인드 풀이
int N, M, t, num, input, first;
vector<int> init;
cin >> N >> M;
isLie.assign(N + 1, true);
parent.assign(N + 1, -1);
party_info.assign(M, vector<int>(0));
cin >> t;
init.assign(t, 0);
for (int i = 0; i < t; i++) { //처음에 주어진 진실을 아는 사람
cin >> init[i];
isLie[init[i]] = false;
}
for (int i = 0; i < M; i++) {
cin >> num >> first;
party_info[i].push_back(first); //각 파티의 첫번째 원소
for (int j = 0; j < num - 1; j++) { //입력 받으면서 유니온
cin >> input;
party_info[i].push_back(input);
unionInput(first, input);
}
}
for (int i = 0; i < init.size(); i++) { //isLie 갱신
int mark = findParent(init[i]); //isLie가 false인 사람의 부모
for (int j = 1; j < parent.size(); j++) { //부모가 같다면 false 처리
if (findParent(j) == mark)
isLie[j] = false;
}
}
int cnt = 0;
for (int i = 0; i < M; i++) { //파티 정보의 첫번째 사람만 체크해도 됨
if (isLie[party_info[i][0]])
cnt++;
}
cout << cnt;
}유니온 파인드 풀이의 전체 소스코드다.
vector<bool> isLie; //이 사람에게 거짓말을 할 수 있나?
vector<int> parent; //부모 정보
vector<vector<int>> party_info; //파티 정보연결 관계를 저장하던 graph 벡터 대신 각 정점의 부모 정보를 담은 parent 벡터를 넣었다.
parent 벡터는 모두 -1로 초기화 할 것이다.
cin >> t;
init.assign(t, 0);
for (int i = 0; i < t; i++) { //처음에 주어진 진실을 아는 사람
cin >> init[i];
isLie[init[i]] = false;
}아까와 마찬가지로 init 벡터를 채우고
for (int i = 0; i < M; i++) {
cin >> num >> first;
party_info[i].push_back(first); //각 파티의 첫번째 원소
for (int j = 0; j < num - 1; j++) { //입력 받으면서 유니온
cin >> input;
party_info[i].push_back(input);
unionInput(first, input);
}
}이번에는 각 파티의 첫번째 사람을 first 변수에 담고 그 이후의 모든 사람들과 유니온 연산 해준다.
예를 들어 4 1 2 3 4 라면 4명의 사람이 파티에 있고 그 사람은 1, 2, 3, 4라는 뜻이다.
first에는 1번 사람이 담길테고 1-2, 1-3, 1-4의 유니온 연산을 해주는 것이다.
유니온 파인드 함수는
[백준] 1717번 : 집합의 표현
문제 풀이 유니온 파인드로 푸는 문제다. 약...2년전 자료구조 시간에 배웠는데 그때 당시에는 아는 것도 없고 + 영어 강의고 + 기타 등등의 이유로 개념만 정말 간신히 익힌 것 같다. 지금 내가
myunji.tistory.com
여기와 동일하다.
for (int i = 0; i < init.size(); i++) { //isLie 갱신
int mark = findParent(init[i]); //isLie가 false인 사람의 부모
for (int j = 1; j < parent.size(); j++) { //부모가 같다면 false 처리
if (findParent(j) == mark)
isLie[j] = false;
}
}갱신된 parent 벡터를 살펴보며 isLie가 false였던 사람과 같은 부모로 연결된 사람들의 isLie를 모두 false로 만든다.
int cnt = 0;
for (int i = 0; i < M; i++) { //파티 정보의 첫번째 사람만 체크해도 됨
if (isLie[party_info[i][0]])
cnt++;
}
cout << cnt;dfs와 같은 방식으로 출력한다.
'💻 현생/⛓ 알고리즘' Related Articles
more
Comments