ksjb2897   1년 전

저는 adj_matrix라는 인접행렬을 만들어서, 서로가 원수이면 1이 되도록 관리하였습니다.

근데 다른 사람들 풀이 보니까 enemy[1001] 배열 하나로 풀더라구요.

근데 이러면 한 사람의 원수가 여러명일 수 있는데 여러명이면 정보손실이 나는거 아닌가요? enemy는 한 사람만 저장할 수 있으니까요...

왜 1차원 배열로 원수들을 관리해서 풀 수 있는지 이해하고 싶습니다 ㅠㅠ

zenith82114   1년 전

원수의 원수는 친구이기 때문에 원수를 공유하는 사람들끼리는 친구여야만 합니다. 따라서 각 사람마다 "대표 원수"를 최대 한 명씩만 지정해서 친구로 밝혀진 사람은 자신과, 원수로 밝혀진 사람은 "대표 원수"와 union하면 친구 집단을 모두 추적할 수 있습니다.

ksjb2897   1년 전

아... 이해했습니다..!! 감사합니다!! 어쨋든 유니온 파인드는 집합의 원소 중 단 하나만 가져오면 되는거니까 그런거군요

댓글을 작성하려면 로그인해야 합니다.