도시 분할 계획1 백준 - 도시 분할 계획 1647 MST 관련 문제를 찾아서 풀다가 어떤 알고리즘을 적용해야 되는지는 알겠는데 도저히 사이클의 여부를 확인할 수 있는 방법을 알지 못해서 많이 헤맸다. 그래서 기록을 남기기 위해 적게 되었다. 백준 - 도시 분할 계획 블로그 목차 1. 원리 2. 코드 원리 - 원리는 어떤 노드의 부모가 누군지를 기록하는 배열을 이용하는 것이다.- 예를 들어, (2, 3) 간선을 추가하는 과정이라면, 2의 부모 노드가 누구인지 3의 부모 노드가 누구인지를 찾아서 비교한다.- 만약 다르다면 서로 연결되어 있는 것이 아니기 때문에 (2, 3) 간선을 추가하면 되고, 부모 노드가 같다면 서로는 이미 연결되어 있기 때문에 간선을 추가할 수 없다.- 아! 위의 아이디어가 크루스칼 알고리즘에서 간선을 하나씩 추가할 때, 사이클.. 2025. 2. 9. 이전 1 다음 반응형
아 맞다, 그거
