escapetime   1년 전

안녕하세요. 이 문제를 프림 알고리즘으로 접근해서 풀어봤는데 자꾸 시간 초과가 뜹니다. 

제 프림 방식이 잘못된건지 아님 다른 문제가 있는지 잘 모르겠습니다. 도움 주시면 정말 감사하겠습니다.

gadoz   1년 전

7개월 전 글이라서 다시 보실지 모르겠지만.. 다른 분들 위해 답변 남깁니다.

일단 위의 코드는 오답입니다.

****  1. 시간초과 부분

저도 동일한 문제로 비슷하게 구현했으나 시간초과가 걸려서 제 구현이 잘못되었나 자괴감에 빠져있었는데요. 시간초과를 해결하는 방법은 최적화였습니다.


1) 정답은 파이썬 특성상 느려서 백준에서 시간초과가 안나기 위해서는 최적화가 필요한데 이 때, list와 tuple 간의 차이가 큽니다. 

-> lit[c].append([e,d]) 를 lit[c].append((e,d)) 로 변경해주세요

2) heappush를 할 때, minheap에 세 가지나 push할 필요가 없습니다. 저 같은 경우는, (cost, 다음 edge) 두 개만 저장해주었습니다.

(어디서 왔는지는 중요하지 않습니다. 앞으로 채워나갈 edge만 중요합니다.)

3) 31번 줄에 heappush할 때, 만약 i[1] 이 이미 방문한 노드면 넣어줄 필요가 없습니다. 따라서 not visited[i[1]] 일 때만 heappush를 수행하면 될 것 입니다.

> 1), 2)번 같은 경우는 시간에 있어서 critical 하진 않지만ㅡ 3) 은 시간초과에 critical 한 문제가 있을 것 같습니다.  .

.

.

**** 2. 오답인 부분

+ cnt < a-2를 통해서 가중치가 큰 것을 제외하고 나머지 노드가 연결되면 된다고 생각하시는거 같은데,, 맨 처음 설정하는 vertex에 따라 답이 틀릴 수 있습니다.

일단 맨 처음 기준을 1번 노드로 잡았기 때문에 1번 노드에서 이어지는 길이 엄청 비싼 cost로 연결되는 것이 하나만 있다고 생각하면 반례가 될 것 입니다.

반례 :

3 2

1 2 8

2 3 1

---

정답 : 1

오답 : 8

> 좋은 idea 였지만 오답이 있었네요... 가장간단하게는 안전하게 모든 update되는 모든 cost를 저장하고 sum(cost) - max(cost) 를 하는 방법이 있습니다.

escapetime   9달 전

이번에 다시 알고리즘 공부 하면서 댓글 다신 걸 봤는데 이 문제 볼 때 참고하겠습니다! 댓글 정말 감사합니다!

pilmokim99   2달 전

list를 tuple로만 바꿔도 시간초과나던 것이 통과되네요..

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