[BOJ] 10775

문제

me

.. 어렵다..
분명 하나씩 찾아내는것은 안된다.. 근데 모르겠다.
분리 집합...이라는 힌트를 봐서 분리 집합을 이용하려고 했다.
나는 비행기를 연결하려 했다.
공항을 연결하면 되지 ㅎ..

solution

• union-find
• parent를 이용하자 : gate만큼 parent dictionary를 사용한다.
• 비행기와 부모를 비교해서 최종 부모를 찾는다.
• 그니깐 결론은 1번 게이트를 원하는 뱅기를 위해 도킹 게이트를 넓히는 것. 이름을 1번으로 붙여서 넓힌 것 처럼 보이는 것
• 서로소 집합, 분리 집합

  union-find는 부모를 연결하여 하나의 그래프를 만드는 것인데 우선 0부터 게이트수까지 딕셔너리를 생성한다.
  두번째 예제로 살펴보면 0:0, 1:1, 2:2, 3:3, 4:4 이렇게 생성된다.
  그리고 비행기번호로 반복문을 순회하여 2 2 3 3 4 4 비행기 정보를 사용한다. 비행기번호와 그 부모가 같은 경우 그대로 return하고 해당 비행기와 게이트는 도킹했다는 것을 나타내기 위해
  union 함수를 통해 해당 비행기의 부모를 -1하여 앞 부분과 연결한다. 이 작업을 통해 딕셔너리는 0:0, 1:1, 2:1, 3:3, 4:4 로 변하게 되며 비행기 정보 중 2번째 2를 사용할 때 2의 부모를 찾아 1에 대해 union를 수행해 0:0, 1:0, 2:1, 3:3, 4:4 로 바뀐다.
  요약
  부모를 찾은 다음, 비행기 번호와 부모가 같으면 return (번호에 맞게 도킹)
  union을 통해 앞의 부모(-1 하여서)와 연결

참고