2-7. 그래프 [BOJ 1043번]

다나·2023년 2월 14일
0

코딩테스트 스터디

목록 보기
21/32
post-thumbnail

1. 관련 문제 🎯

문제 : 백준 1043 거짓말 😈
난이도 : 골드 4

2. 문제 소개 🧩

1️⃣ 파티에 갈 때마다, 지민이는 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다.
2️⃣ 지민이는 되도록이면 과장해서 이야기하려고 한다.
3️⃣ 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다.

따라서 지민이는 아래의 일을 모두 피해야 한다.

  • 1) 이야기의 진실을 아는 몇몇 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기해야한다.
  • 2) 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다.

4️⃣ 이야기의 진실을 아는 사람 N명이 주어진다.
5️⃣ 각 파티에 오는 사람들의 번호가 주어진다.
6️⃣ 지민이는 모든 파티에 참가해야 한다.

☝️ 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구해야 한다.

3. 문제 풀이 🖌️

  • 위의 그림만 보면 각 파티별로 진실을 아는 사람의 번호가 있는지를 살펴보고, 진실을 아는 사람이 있는 파티에 참석한 사람의 경우 똑같이 진실을 아는 사람 된다고 생각할 수 있다!

그러면 왜 그래프 관련 문제일까?? 🤔

  • 아래의 예시를 보면 알 수 있다!!
  • 위에서 말한 대로 각 파티별로 진실을 아는 사람의 번호가 있는 경우 진실을 말하고, 없는 경우 진실을 말하지 않는다고 해보자~
    그러면, 아래와 같은 경우 진실을 말하지 않는 파티는 총 3개가 된다.

그러나 정답은 바로 바로 3이 아닌 '2'임을 알 수 있다!!

따라서, 한 가지를 더 생각해줘야 한다🥲

  • 각 파티는 위에서 아래로 순서대로 열리는 것이 아니므로, 진실을 아는 사람과 같은 파티에 참석한 사람은 어느 파티에서도 진실을 아는 사람이 된다.
  • 따라서, 아래와 같이 처음부터 진실을 아는 사람인 1번과 같이 파티를 참석한 4번은 4번 단독으로 파티를 참가해도 진실만을 말해야 한다!!

위의 사진에서 오른쪽 그래프처럼 1번과 4번을 묶을 수 있다.

정리해보면
☝️ 각각의 파티를 보면서, 같이 파티를 한 사람을 하나의 그래프(그룹)로 묶는다.
✌️ 각각의 파티를 다시 한 번 살펴보면서, 해당 파티에 참석한 사람들 중에 진실을 아는 사람과 같은 그룹이 있는 경우 해당 파티는 진실을 말해야 한다.

3-1. 각각의 파티를 보면서, 같이 파티를 한 사람을 하나의 그래프로 묶는다.

☝️ 이때, Union-Find를 사용하여 같은 그룹으로 묶을 수 있다.
Union-Find 관련 내용은 https://velog.io/@da_na/2-3.-그리디-프로그래머스-섬-연결하기 를 참고하세요~!

int parent[51] = {0,};
vector<int> party[M];  //각 파티마다 오는 사람들의 번호

int find(int x){	//속한 그룹의 번호를 반환한다.
    if(parent[x] == x){
        return x;
    }
    return parent[x] = find(parent[x]);
}

void merge(int x, int y){	//같은 그룹으로 묶는다.
    int X = find(x);
    int Y = find(y);
    if(X == Y) return;
    parent[Y] = X;
}

for(int m=0; m<M; m++){
	cin>>partyNums;
        
	for(int i=0; i<partyNums; i++){
    	//파티에 참석한 사람들을 2번 살펴봐야 하므로 vector안에 저장해놓는다.
    	cin>>nums;
        party[m].push_back(nums);
    }

    for(int i=0; i<partyNums-1; i++){
    	// 같은 파티에 참석한 사람들끼리 같은 그룹으로 묶는다.
    	int x = party[m][i];
        int y = party[m][i+1];
        merge(x,y);
    }
}

3-2. 각각의 파티를 다시 한 번 살펴보면서, 해당 파티에 참석한 사람들 중에 진실을 아는 사람과 같은 그룹이 있는 경우 해당 파티는 진실을 말해야 한다.

bool is_parent(int x, int y){ //같은 그룹인지를 살펴본다.
    int X = find(x);
    int Y = find(y);

    if(X == Y) return true;
    return false;
}

for(int i=0; i<M; i++){    //각각의 파티마다 진실을 아는 사람이 있는지 살펴본다.
        bool check = false;
        answer++;
        for(int j=0; j<party[i].size(); j++){
            for(int k=0; k<truthPeopleNums; k++){
            	//해당 파티에 진실을 아는 사람과 같은 그룹에 속한 사람이 있는 경우, 해당 파티는 진실을 말한다.
                if(is_parent(parent[party[i][j]], parent[truthPeople[k]])){
                    answer--;
                    check = true;
                    break;
                }
            }
            if(check == true){
                break;
            }
        }
    }

4. 전체 코드 🔑

#include <iostream>
#include <vector>
using namespace std;

int parent[51] = {0,};

int find(int x){	//속한 그룹의 번호를 반환한다.
    if(parent[x] == x){
        return x;
    }
    return parent[x] = find(parent[x]);
}

void merge(int x, int y){	//같은 그룹으로 묶는다.
    int X = find(x);
    int Y = find(y);
    if(X == Y) return;
    parent[Y] = X;
}

bool is_parent(int x, int y){ //같은 그룹인지를 살펴본다.
    int X = find(x);
    int Y = find(y);

    if(X == Y) return true;
    return false;
}

int main() {
    std::ios::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);

   int N = 0, M = 0;    //사람의 수, 파티의 수
    cin >> N >> M;

   int truthPeopleNums = 0; //이야기의 진실을 아는 사람의 수
   vector<int> truthPeople; //이야기의 진실을 아는 사람들의 번호
   vector<int> party[M];  //각 파티마다 오는 사람들의 번호
   
   int nums;
   cin >> truthPeopleNums;
   
    for(int i=0; i<truthPeopleNums; i++){
        cin>>nums;
        truthPeople.push_back(nums);
   }

   int partyNums = 0;   //각 파티마다 오는 사람의 수
   int answer = 0;
   
   for(int i=1; i<=N; i++){
        parent[i] = i;
   }

    for(int m=0; m<M; m++){
        cin>>partyNums;
        
        for(int i=0; i<partyNums; i++){
            cin>>nums;
            party[m].push_back(nums);
        }

        for(int i=0; i<partyNums-1; i++){
            int x = party[m][i];
            int y = party[m][i+1];
            merge(x,y);
        }
    }

    for(int i=0; i<M; i++){    //각각의 파티마다 진실을 아는 사람이 있는지 살펴본다.
        bool check = false;
        answer++;
        for(int j=0; j<party[i].size(); j++){
            for(int k=0; k<truthPeopleNums; k++){
            	//해당 파티에 진실을 아는 사람과 같은 그룹에 속한 사람이 있는 경우, 해당 파티는 진실을 말한다.
                if(is_parent(parent[party[i][j]], parent[truthPeople[k]])){
                    answer--;
                    check = true;
                    break;
                }
            }
            if(check == true){
                break;
            }
        }
    }
    cout<<answer<<"\n";
}

5. 결과 🏆

profile
컴퓨터공학과 학생이며, 백엔드 개발자입니다🐰

0개의 댓글