![](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FMpCza%2FbtrJ1H9UOh3%2F3qunvri4iMnI6UvnNsYF3K%2Fimg.png)
[BOJ/백준] 1043 거짓말 - 파이썬
·
💻 알고리즘/PS
문제 진실을 알고 있는 사람이 파티에 오는 경우, 진실을 알고 있는 사람과 같은 파티에 왔던 사람이 다른 파티에 오는 경우, 거기에 있는 다른 사람이 참석하는 또 다른 파티의 경우 등이 존재하는 상황에서 지민이가 과장된 이야기를 할 수 있는 파티 수의 최댓값을 구하는 문제. 문제풀이 Union-Find 알고리즘으로 풀이 지민이가 과장된 이야기를 할 수 없는 사람들을 하나의 집합으로 구성 ffind 함수로 해당 원소의 parent 원소를 찾는다. union 함수로 진실을 아는 사람들과 그와 같이 파티에 오는 사람들(연쇄적)을 하나로 묶는다. - 입력받은 두 원소가 모두 진실을 아는 사람 -> 변화 X - 둘 중 한 원소가 진실을 아는 사람 -> 진실을 아는 사람을 부모로 갱신 - 둘 다 진실을 아는 사람이..