1922번 - 네트워크 연결
안녕하세요. 크루스칼 알고리즘을 생각한대로 코드로 짰는데 무엇이 문제인지 모르겠습니다.
일단 순서는 다음과 같습니다.
엣지를 추가할 때 싸이클이 생기는 것을 방지하기 위해 set배열과 list라는 링크드 리스트를 사용하는데,
엣지를 추가할 때마다 각각의 from과 to를 집합(그룹)을 만들어 줌으로써 싸이클을 방지하도록 하였습니다.
4 개의 케이스가 존재합니다. 순서대로 설명하겠습니다.
1. 둘 다 그룹이 없는 경우 (ex. (2 3 2), (4 5 3))
set[2]와 set[3]을 첫 번째 컴퓨터의 번호인 2로 그룹넘버를 설정하고 list[2]->2->3 이런식으로 됩니다.
set[4]와 set[5]를 첫 번째 컴퓨터의 번호인 4로 그룹 넘버를 설정하고 list[4]->4->5 이런식으로 됩니다.
list[x]마다 head와 tail 포인터가 있어 head는 첫번째 vertex를, tail은 마지막 vertex를 가리키도록 합니다.
2. 하나는 그룹이 있는데 하나는 그룹이 없는 경우( ex. 1 3 3)
set[3]이 2이고 1의 그룹 넘버가 없으므로 set[1]을 set[3]과 동일한 2로 하고 list[2]->2->3->1 이렇게 추가합니다.
3. 둘 다 그룹이 있는데 그룹 넘버가 다를경우 ( ex. 3 4 6)
set[3]은 2, set[4]가 4이므로 그룹 넘버가 다르므로 한 쪽 그룹에서 다른 한 쪽으로 멤버를 다 옮겨줍니다.
옮기기 전, list[2]->2->3->1, list[4]->4->5 이고 set배열은 {0,2,2,2,4,4} 이렇게 되어 있습니다.
옮긴 후에는 list[2]는 null, list[4]->4->5->2->3->1이 되고 set 배열은 {0,4,4,4,4,4}가 됩니다.
4. 둘 다 그룹이 있는데 그룹 넘버가 같을 경우 (ex. 2 4 8)
set[2]와 set[4] 둘 다 4로 같으므로 둘을 연결하면 싸이클이 형성됩니다. 따라서 아무 일도 하지 않고 그다음 엣지로 넘어갑니다.
프로그램을 돌리면 "틀렸습니다"라고 뜹니다. 그래서 답이 잘 못 되게 나오는 것 같은데, 어느 부분에서 문제가 생기는 지
모르겠습니다. 부탁합니다. 도와주세요!!
댓글을 작성하려면 로그인해야 합니다.
gounttt 7년 전
안녕하세요. 크루스칼 알고리즘을 생각한대로 코드로 짰는데 무엇이 문제인지 모르겠습니다.
일단 순서는 다음과 같습니다.
엣지를 추가할 때 싸이클이 생기는 것을 방지하기 위해 set배열과 list라는 링크드 리스트를 사용하는데,
엣지를 추가할 때마다 각각의 from과 to를 집합(그룹)을 만들어 줌으로써 싸이클을 방지하도록 하였습니다.
4 개의 케이스가 존재합니다. 순서대로 설명하겠습니다.
1. 둘 다 그룹이 없는 경우 (ex. (2 3 2), (4 5 3))
set[2]와 set[3]을 첫 번째 컴퓨터의 번호인 2로 그룹넘버를 설정하고 list[2]->2->3 이런식으로 됩니다.
set[4]와 set[5]를 첫 번째 컴퓨터의 번호인 4로 그룹 넘버를 설정하고 list[4]->4->5 이런식으로 됩니다.
list[x]마다 head와 tail 포인터가 있어 head는 첫번째 vertex를, tail은 마지막 vertex를 가리키도록 합니다.
2. 하나는 그룹이 있는데 하나는 그룹이 없는 경우( ex. 1 3 3)
set[3]이 2이고 1의 그룹 넘버가 없으므로 set[1]을 set[3]과 동일한 2로 하고 list[2]->2->3->1 이렇게 추가합니다.
3. 둘 다 그룹이 있는데 그룹 넘버가 다를경우 ( ex. 3 4 6)
set[3]은 2, set[4]가 4이므로 그룹 넘버가 다르므로 한 쪽 그룹에서 다른 한 쪽으로 멤버를 다 옮겨줍니다.
옮기기 전, list[2]->2->3->1, list[4]->4->5 이고 set배열은 {0,2,2,2,4,4} 이렇게 되어 있습니다.
옮긴 후에는 list[2]는 null, list[4]->4->5->2->3->1이 되고 set 배열은 {0,4,4,4,4,4}가 됩니다.
4. 둘 다 그룹이 있는데 그룹 넘버가 같을 경우 (ex. 2 4 8)
set[2]와 set[4] 둘 다 4로 같으므로 둘을 연결하면 싸이클이 형성됩니다. 따라서 아무 일도 하지 않고 그다음 엣지로 넘어갑니다.
프로그램을 돌리면 "틀렸습니다"라고 뜹니다. 그래서 답이 잘 못 되게 나오는 것 같은데, 어느 부분에서 문제가 생기는 지
모르겠습니다. 부탁합니다. 도와주세요!!