이 문제는 이분그래프 문제와 비슷하게 color변수를 이용해서(1 or 2) dfs나 bfs로 색칠하면서 이분그래프가 맞는지 아닌지 판별하는 식으로 풀 수 있는데, 이번에는 Union-Find(disjoint-set이었나? 아마..)를 이용해서 풀어보려고 하다가 막히게 되었다.
입력으로 들어오는 것이 parent가 서로 다르면 서로 다른 그룹에 넣고, parent가 서로 같으면 이분 그래프가 아닌 것이고... 이렇게 하려고 했는데, 막상 구현해보니 조금 코드가 지저분해질 것 같아서 -> 계속 하다보니 이렇게 할 경우 안될 것 같다... 그룹을 특정한 수로 지정해놓을 경우에는 나중에는 같은 그룹이 될 수 있는데도 이미 특정한 수로 지정해둬서 안될 수 있다.
하지만 koosaga님 방식처럼 특정한 수로 그룹을 지정해놓는 것이 아니라 그냥 두 분류로 나눴다가 알아서 합쳐지도록 하는 것이면 괜찮은 것 같다. 좀 어렵지만 멋지다...
고수분들의 코드를 참고하는 중이었는데, koosaga님의 코드를 보게 되었다. 역시 Union-Find를 이용해서 구현하셨는데, 정말 깔끔하고 간단하게 구현하셨다. 솔직히 말해서 완벽히 이해하진 못한 것 같은데, 어느정도만 이해했는데도 아름답다...
koosaga님의 방식은 얼핏 보면 입력 받은 것끼리 같은 그룹으로 Union하는 것 같아 보이지만 사실은 그렇지 않다. a, b가 들어오면 Union(a, b)를 하는게 아니라 Union(a, b+n), Union(b, a+n)이렇게 두 번 함으로써 a, b는 서로 다른 그룹에 속하게 된다!!! 그림을 그려보면 더 이해하기 쉬울 것이다.
그리고 마지막으로 이분 그래프인지 아닌지를 판별할 때는 자기 자신에 n을 더한 값을 다른 그룹에 넣어 놨으므로 자기자신과 자기자신+n값이 같은 그룹에 있는지 아닌지를 판별해 보면 된다.
댓글 없음:
댓글 쓰기