공통

유니온할 때, 어차피 같은 집합이므로 연결되는 두 정점씩 할 필요 없이 (첫 시작 정점, 현재 정점) 으로 해도 됨

• 12100 (2048 (Easy))
  • 움직이는 함수는 하나만 짜고, 보드를 상, 하, 좌, 우 방향으로 돌려가면서 모든 방향의 움직임을 구현할 수 있음 (샘플코드 참조)
  • 중복되어 많이 사용되는 자료형은 별명을 붙여 사용하기
  • 움직이는 부분 구현 시 복잡하게 짜지 않도록. O(n^2)으로 구현하기
  • 백트래킹 구현 시, 원 상태로 되돌리는 부분 주의하기 (매개변수 활용한 경우 주소값으로 넘겨줘서 배열의 값이 달라지진 않았는지 확인)
• 16114 (화살표 연산자)
  • 문자열을 반환하도록 함수화하기
• 20040 (사이클 게임)
  • union 연산 함수를 bool 반환형으로 만들면 사이클이 발생하는 순간을 판단하기 좋음
• 호텔 방 배정
  • (c++) 효율성에서 시간초과 난다면 unordered_map 사용하기
• 1043 (거짓말)
  • 진실을 아는 사람들은 루트 정점을 0으로 설정해 같은 집합으로 묶고 시작하기
  • 각 파티의 사람들은 한 집합으로 묶여져 있으므로 각 파티에서 한 사람만 저장해둔 뒤, 마지막에 거짓말 가능 여부 한 번에 판단하기
• 4195 (친구 네트워크)
  • weighted union find 알고리즘을 활용해, 하나의 parent 배열에 친구 수도 같이 저장하기
• 20303 (할로윈의 양아치)
  • 1차원 냅색 알고리즘으로 구현하기