ds04030   1년 전

게시글에 있는 질문글은 다 읽어보았고 반례도 통과합니다.

저는 플로이드 와샬 알고리즘으로 풀이하였습니다.

그런데 틀렸다고 나옵니다.

이 문제는 그래서 출발점이 무조건 1이라는 건지  X노드라는 건지 모르겠네요..


출발점이 1인가요  X인가요?

shg9411   1년 전

어떤 점이든 상관 없습니다.

ds04030   1년 전

흠..

아래처럼 시작 노드를 1 (int start = 1)로 지정해주니 맞다고 뜨네요..

제가 36번째 줄처럼 1번 노트~N번째 노드까지 탐색하니까 시간초과가 뜨구요..

이거 문제를 그냥 시작노드는 1이라고 해야하는거 아닌가요?

지금 오타/요청을 할수가 없어서 누가 나중에 요청좀 해주시면 감사하겠습니다.

shg9411   1년 전

전에 하셨던 질문이랑 일맥상통하지 않습니다.

출발점이 무조건 1이라는 건지 x노드라는 건지 물어보셨었고, 어느 점을 출발점으로 잡던 상관 없다고 말씀드렸습니다.

출발점을 어느 점으로 잡는지랑, 모든 정점에 대해서 계산하는 것이랑은 이 문제 기준으로 최대 500배 차이가 나겠죠.

ds04030   1년 전

출발점을 N으로 잡고 N개의 정점에 대하여 벨만포드를 풀어야 하는건지(벨만포드 알고리즘을 N번 수행)

출발점을 1로 잡고 N개의 정점에 대하여 벨만포드를 풀어야하는건지 궁금했습니다.(벨만포드 알고리즘을 1번 수행)

저는 전자라고 생각하였으나 후자가 맞았습니다..

pichulia   1년 전

게시판에 올려두신 코드는 시작점이 어디라도 상관없이 음수사이클이 있으면 yes를 출력하는 코드가 맞습니다.

dist값이 0이 아니라 INF에서 시작하는 음수사이클일 뿐이죠.



이 코드를 틀리게 만드는 데이터를 찾고있는데 쉽진 않네요ㅠ

ds04030   1년 전

제가 올린 두번째 코드가 시작점이 어디라도 상관없이 음수사이클이 있으면 yes를 출력하는 코드라고 말씀하시는거죠 ?

(제가 올린 두번째 코드를 아직 보지 않으셨다면, 봐주시면 감사하겠습니다^^ 두번째 코드로 통과하였습니다)

반례를 찾아주고 계신다니.. 정말 감사합니다. 다른분들에게도 많은 도움이 될것 같습니다.

pichulia   1년 전

조금 고민해봤는데 그냥 맞는 코드인거 같습니다.

그 증거로 dist[start]=0; 부분을 지워도 정답을 받습니다.


따라서 지문을 수정할 필요가 없습니다.

ds04030   1년 전

아 !! 결국은

시작점이 어디든간에 음수 싸이클만 있다는 것을 확인하면 "yes'" 라는 거군요?

그래서 dist[start]=0; 을 지워도 되는 것이구요..

또한 56번째줄에 if(cycle || dist[start] < 0) ans = true;  에서

dist[start]<0 조건을 뺀 if(cycle) 만 해도 정답처리가 되네요


감사합니다.

yhs05323   3달 전

저는 플로이드 워셜로만 풀린다고 생각했는데 벨만 포드로 가능한가보네요.

저는 1과 연결되어 있지 않은 노드가 있다면 그 노드의 음수 사이클을 벨만포드 알고리즘으로 발견 할 수 없다 생각했습니다. 이 생각이 틀린 건가요??

아 헷갈립니다. 공부가 많이 부족한가봐요..

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