8-P 1219 오민식의 고민 하나 질문드립니다.
안녕하세요 강사님. 강의 항상 잘 듣고 있습니다. 오민식의 고민 풀이방법 하나 질문드립니다.
풀다가 결국 답안을 보니 양의 사이클이 끝점으로 이어지는지를 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;
}
이부분을 플로이드워셜로 하셨다는거죠? 전체 코드 부탁드립니다.
감사합니다.
강사 큰돌 올림.
0
인프런 코드블록을 어케 만드는지 모르겠어서 링크로 드릴께요!! 주석도 좀 달아놨습니다
https://www.acmicpc.net/source/46302418
근데... 맞네요...??? 고친게 없는데 왜 맞는건지;;
0
앞으로는 링크로 주시면 됩니다. 위 링크를 통해 코드를 보는게 더 좋아요. ㅎㅎ 잘 하셨습니다. 인프런 코드블록은.. 쓰레기에요 ㅠ
일단 로직상 다 맞습니다. 벨만 + 플로 했는데 플로이드 워셜같은 경우 도착점까지의 경로를 확인할 수 있기 때문에 로직상은 옳은 코드죠.
but, 너무나도 시간복잡도가 많이 걸리는 로직입니다. 플로이드워셜의 경우 시간복잡도는 O(V^3)이죠? 지금 N의 범위는 50이기 때문에 sh님이 작성하신 코드는 125000 정도의 시간복잡도를 가지게 되죠. 뭐 사실 10만 정도라 괜찮긴 해서 통과가 된 것같아요.
BFS로도 한번 풀어보시는 것을 추천드리고.
잘 짜셨습니다.
감사합니다.
강사 큰돌 올림.
1-E질문입니다!
0
533
2
3-L 틀린 부분 피드백 부탁드립니다.
0
836
2
1-A문제 순열재귀함수 질문입니다.
0
396
1
1-A 일곱난쟁이문제입니다
0
471
1
문제 풀 때 방향성에 대해
0
811
1
맥에서 vs code로 실행 관련 질문입니다
0
530
1
17071번 메모리 초과
0
390
1
1-C질문입니다!
0
428
2
2-B BFS 시간초과질문
0
638
2
1-O 13번 라인
0
447
1
6-J 놀이공원 문제 질문
0
390
1
구현관련 질문
0
492
1
강의 교안
0
322
1
실력을 더 올리고나서 강의를 보는 것이 맞을까요?
0
550
1
안녕하세요! 재귀함수에 관해서 질문드립니다
0
540
1
1-K
0
481
2
3-G번 질문있습니다.
1
482
3
3-C 실행 시간 질문드립니다.
0
504
1
4-A 문제 풀이 질문있습니다.
0
602
2
비트마스킹 연산자 "1의 보수" 영문 표기법
0
441
1
격자탐색 문제에서 BFS 시간복잡도 질문드립니다.
0
349
1
3-O go 함수 질문 드립니다.
1
453
2
4-A 출력 질문
0
308
1
1주차 1-O 질문드립니다
0
266
1