rdd6584   2달 전

밑에는 제 프림 코드입니다.


prim(0, n)일 때는 정답

prim(4, n)일 떄는 오답 

prim(9, n)일 떄는 정답 이런식으로 매우 불안정한 값들이 나왔습니다.

크루스칼로 작성한 코드도 오답처리 되었구요.


아마도 간선중에 같은 값이 있을 경우 경우에따라 각각 다른 트리가 만들어져서 이런 현상이 발생하는거 같은데

완벽하게 문제를 해결할 수 있는 알고리즘이 있을까요?

rdd6584   2달 전

혹은 문제가 없다면, 제 코드에서 어떤점이 틀린걸까요?

rhs0266   2달 전

프림은 간선을 n-1번 추가합니다.

n번째 get min vertex 호출의 리턴값이 쓰레기값일수가 있네요

rdd6584   2달 전

답변 감사합니다.

그런데 맨처음에 dist에 0값이 들어가기 때문에 n번째에 끝나야하는게 맞지않나요?


그리고 제 밑에 n-1번 더했을때 멈추는 또다른 프림코드에서도 같은 prim 시작정점에 따라서 같은 결과를 보이네요..

rhs0266   2달 전

그렇군요...

혹시  윗코드에서

#define INF 1001L

로 고쳐보실래요? 

rhs0266   2달 전

c에 대한 제한이 따로 없군요

그러면 0x7fffffff 라던가..?

1000 미만이라는 보장이 없으니까요 ㅜㅜ

rdd6584   2달 전

답변 감사합니다

1000000000L로 바꿔도 결과는 동일하네요 ㅠㅠ

밑에 또다른코드는 INF가 아니라 방문 못하는곳을 0으로 설정했는데도 위코드와 같은 진입정점에 대해서 동일한 결과를 보이네요.. ㅠㅠㅠㅠ

 

rdd6584   2달 전

sum 자료형을 long long이 아닌 int로만 해줘도 케이스는 통과하는듯 해요

rhs0266   2달 전

다행이네요 >_<

간선 길이 중에서 정확히 1000 인 경우가 있었나봅니다~

rdd6584   2달 전

ㅠㅠ 말을 잘못했나봐요.

그게 여전히 prim(0) 등은 통과되는데 prim(5)등은 통과하지 못하는 현상은 발생합니다.


sum 자료형을 long long이 아닌 int로만 해줘도 케이스는 통과하는듯 해요 << 이 말은 연결비용이 그리 크지 않다는 뜻에서 말씀드렸어요.

rhs0266   2달 전

그건 당연히 n<=5 인 경우가 입력에 있어서 그렇지 않을까요~?

rdd6584   2달 전

아 그럴수도 있겠네요.

그런데 제 질문의 요지가 그런 현상에 대해서 여쭤본거였는데요.

prim(9) 이렇게 하면 또 정답처리가 되더랍니다.. ㅠㅠㅠ

rdd6584   2달 전

아 아니네요.. 제가 착각했나봐요.

prim(5)부터는 오답이뜨네요 정말감사합니다.

혹시 이 문제의 제가 올린 또다른 질문 크루스칼에 대해서도 봐주실수 있나요?

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