28121번 - 산책과 쿼리
문제 풀다가 홀수 사이클이 있어야 한다는 것도 깨달았고,
그러면서 색칠을 해서 같은 색끼리 연결이 될 때 홀수 사이클이 생겨난다는 것을 깨달았습니다.
그래서 저는 연결할때마다 색을 칠하고, 만약 분리된 그룹이라면 다른 색으로 처음에 칠했다가,
두 그룹이 연결이 될 때 색을 유니온 파인드로 통합하는 식으로 설계했습니다.
예를 들어, 1 2 3 4가 있고 처음에 1과 2, 3과 4를 결합하여,
1의 색 : 1
2의 색 : 2
3의 색 : 3
4의 색 : 4
로 만들고,
그다음 1과 3을 결합하면,
1과 4, 2와 3을 유니온파인드로 결합하여
1-4 // 2-3으로 2가지의 집합이 나오도록 하고, 색을 묶었습니다.
근데 보니깐 0과 1로만 가지고 판단을 할 수 있고 코드를 짤 수 있는 것 같더라구여.
처음에 1과2, 3과4를 결합하여
1의 색 : 0
2의 색 : 1
3의 색 : 0
4의 색 : 1
로 만들고, 1과 3을 결합할 때, 3과4에 색반전을 주어서 관리하는 것 같던데,
근데 이렇게 보면 3과 4의 모든 색을 돌아다니면서 0과 1을 서로 반전시키는 건 시간복잡도가 클 것 같고,
그래서 한번에 집합 별로 처리하기에는, 어쨋든 1, 2, 3, 4 모두가 유니온 파인드로 합쳐질텐데, 그러면 반전에 대한 정보가 3, 4만이 아니라 1, 2, 3, 4전부에게 영향을 주어서 반전처리의 의미가 없어지는거 아닌가여..??
어떻게 색 2개만을 가지고 홀수 사이클을 탐지할 수 있을지 모르겠습니다 ㅠㅠ
https://justicehui.github.io/m...
항상 답변 감사합니다 ㅠㅠ 이해 됐습니다..! 정점을 2개로 나누는게 기발하네요,,
댓글을 작성하려면 로그인해야 합니다.
ksjb2897 1년 전
문제 풀다가 홀수 사이클이 있어야 한다는 것도 깨달았고,
그러면서 색칠을 해서 같은 색끼리 연결이 될 때 홀수 사이클이 생겨난다는 것을 깨달았습니다.
그래서 저는 연결할때마다 색을 칠하고, 만약 분리된 그룹이라면 다른 색으로 처음에 칠했다가,
두 그룹이 연결이 될 때 색을 유니온 파인드로 통합하는 식으로 설계했습니다.
예를 들어, 1 2 3 4가 있고 처음에 1과 2, 3과 4를 결합하여,
1의 색 : 1
2의 색 : 2
3의 색 : 3
4의 색 : 4
로 만들고,
그다음 1과 3을 결합하면,
1과 4, 2와 3을 유니온파인드로 결합하여
1-4 // 2-3으로 2가지의 집합이 나오도록 하고, 색을 묶었습니다.
근데 보니깐 0과 1로만 가지고 판단을 할 수 있고 코드를 짤 수 있는 것 같더라구여.
처음에 1과2, 3과4를 결합하여
1의 색 : 0
2의 색 : 1
3의 색 : 0
4의 색 : 1
로 만들고, 1과 3을 결합할 때, 3과4에 색반전을 주어서 관리하는 것 같던데,
근데 이렇게 보면 3과 4의 모든 색을 돌아다니면서 0과 1을 서로 반전시키는 건 시간복잡도가 클 것 같고,
그래서 한번에 집합 별로 처리하기에는, 어쨋든 1, 2, 3, 4 모두가 유니온 파인드로 합쳐질텐데, 그러면 반전에 대한 정보가 3, 4만이 아니라 1, 2, 3, 4전부에게 영향을 주어서 반전처리의 의미가 없어지는거 아닌가여..??
어떻게 색 2개만을 가지고 홀수 사이클을 탐지할 수 있을지 모르겠습니다 ㅠㅠ