인프런 커뮤니티 질문&답변
작성한 질문수
8-P 1219 오민식의 고민 하나 질문드립니다.
해결된 질문
작성
·
218
0
안녕하세요 강사님. 강의 항상 잘 듣고 있습니다. 오민식의 고민 풀이방법 하나 질문드립니다.
풀다가 결국 답안을 보니 양의 사이클이 끝점으로 이어지는지를 bfs로 판별하셨더라구요
저는 마지막에 한번 더 사이클이 존재하는지 확인하는 방법을 다음과 같이 하려고 했었는데요
1. 플로이드 워셜로 dist 2d vector를 미리 만들어놓고
2. 사이클이 감지되는 간선의 끝부분과 도착도시의 dist vector가 유효한 값인지 확인
3. 유효한 값이라면 양의 사이클이 도착도시까지 이어지므로 Gee 출력
일단 현재 계속 50퍼에서 틀렸다고 뜨길래... 풀이 방향이 아예 틀린건지가 궁금합니다...
답변 주시면 감사하겠습니다.
답변 1
1
안녕하세요. ㅎㅎ
음 그니까
while(q.size()){
int here = q.front(); q.pop();
for(pair<int, int> there : adj[here]){
if(there.first == e){
ok = 1; break;
}
if(!visited[there.first]){
visited[there.first] = 1;
q.push(there.first);
}
}
if(ok) break;
}
이부분을 플로이드워셜로 하셨다는거죠? 전체 코드 부탁드립니다.
감사합니다.
강사 큰돌 올림.
앞으로는 링크로 주시면 됩니다. 위 링크를 통해 코드를 보는게 더 좋아요. ㅎㅎ 잘 하셨습니다. 인프런 코드블록은.. 쓰레기에요 ㅠ
일단 로직상 다 맞습니다. 벨만 + 플로 했는데 플로이드 워셜같은 경우 도착점까지의 경로를 확인할 수 있기 때문에 로직상은 옳은 코드죠.
but, 너무나도 시간복잡도가 많이 걸리는 로직입니다. 플로이드워셜의 경우 시간복잡도는 O(V^3)이죠? 지금 N의 범위는 50이기 때문에 sh님이 작성하신 코드는 125000 정도의 시간복잡도를 가지게 되죠. 뭐 사실 10만 정도라 괜찮긴 해서 통과가 된 것같아요.
BFS로도 한번 풀어보시는 것을 추천드리고.
잘 짜셨습니다.
감사합니다.
강사 큰돌 올림.
인프런 코드블록을 어케 만드는지 모르겠어서 링크로 드릴께요!! 주석도 좀 달아놨습니다
https://www.acmicpc.net/source/46302418
근데... 맞네요...??? 고친게 없는데 왜 맞는건지;;