백준 1043 거짓말, 유니온파인드 swift언어 문제풀이

 

 

백준 1043번 거짓말 문제링크 ▼

1043번: 거짓말

 

 

---

백준 1043번 거짓말 문제 개요

해당문제는 solved.ac 골드 수준의 문제로 분류되고 있습니다.

내용을 보자면, 사람의 수 N과 지민이 이야기의 진실을 하는 사람 리스트, 각 파티에 오는 사람들의 번호가 주어질때, 과장된 이야기를 할 수 있는 파티의 최대 갯수를 반환하는 문제입니다. 지민이의 진실을 알고 있는 사람들에게는 절대 과장된 이야기를 하면 안됩니다.

지민이의 진실을 알지 못하는 사람에게만 과장된 얘기를 하기 위해서는 진실을 알고 있었던, 전파되어 알게되는 모든 사람들을 식별할 필요가 있습니다. 이를 유니온파인드(Union Find)방법을 통해서 알아낼 수 있습니다. 

바로 swift 코드와 함께 문제풀이를 가보겠습니다.

 

 

---

백준 solved.ac 골드티어문제, 거짓말 swift 풀이

먼저, 미리 한 줄을 입력받아 [Int]타입의 리스트를 반환하는 클로져를 구현했습니다.

 

 

 

 

각 사람의 번호를 인덱스로 해서 해당 번호에 대한 부모노드를 찾아주는 메서드입니다. 밑에 설명할 mergeParent에서 부모노드가 통합되면, parents[node] == node가 성립하지 않을 수 있는데, 이럴 경우에는 현재 부모노드를 찾기 위해 20행과 같이 재귀를 실행해서 반환합니다.

 

 

 

 

부모노드를 통합하는 mergeParent 메서드입니다. 통일된 기준으로 두개의 노드에 대한 부모노드를 동일하게 만들어줍니다. 가령, 지민이의 진실을 알고 있는 사람의 번호, 진실을 모르는 사람의 번호가 위 메서드로 merge될 경우, 이 두명은 전부 진실을 알고 있는 부모노드로 통합됩니다.

 

 

 

 

이제 입력을 받습니다. 첫줄에는 N, M을 입력받았습니다. 두번째 줄에는 진실을 알고있는 사람의 수, 진실을 알고 있는 번호 리스트를 입력받습니다.

37행) G에는 각 파티 별 참석하는 사람들의 번호를 기록합니다.
38행) parents 배열은 각각의 번호를 인덱스로 대응하여 부모노드를 반환하는데 사용할 배열입니다. 초기 각 번호의 부모노드는 개인 번호에 대응되며, mergeParent로 부모노드가 통합되면서 부모노드값이 갱신될 예정입니다.
39 ~ 41행) 지민이의 진실을 알고있는 리스트를 만들어둡니다.

 

 

 

 

각 파티에 참석하는 참석자 번호의 부모노드를 하나하나 통합해나가는 과정입니다. 이 과정에서 knowList,

50행) 지민이의 진실을 알고 있는 사람들의 번호와 엮인 사람들은 모두 같은 부모노드를 갖게 될 것입니다. 그렇게 이후 과정에서 진실을 알고 있는 사람들을 분간할 수 있고, 과장해도 되는 파티의 수를 알 수 있습니다.

 

 

 

 

앞서 부모노드 통합과정을 거쳤으므로, 이제 남은 것은 각 파티별로 참여한 참석자들에 대해서 하나하나 knowList 사람들의 부모노드와 동일한지 확인해보면 됩니다. 만약 knowList 사람들 중 어느하나라도 같은 부모노드를 갖고 있다면 지민이의 진실을 알고 있는 사람이므로, 과장된 말을 해서는 안되는 파티입니다. 이를 통해서 answer값을 누적하고, 결과값으로 출력하며 문제를 해결합니다. 

 

---

지금까지 백준 solved.ac 골드티어, 1043 거짓말 문제를 유니온파인드(union find) 를 활용하여 swift 언어로 풀어봤습니다. 관련 질문이나 의견 지적 언제든 댓글로 환영합니다. 즐거운 코딩 되세요.

 

 

소스코드 첨부 링크 ▼

GitHub - applebuddy/BJAlgorithmStudy: Uploading BaekJoon Algorithm Study Codes $