3-k 3197 질문드립니다!
70
작성한 질문수 4
https://www.acmicpc.net/source/84329800
항상 재미난 강의 감사드립니다 :)
강의듣기전에 문제를 먼저 풀어보았는데요!
예제 3개는 잘 통과하였는데, 백준에 문제를 제출하니 시간초과라고 뜹니다..!
DFS 탐색으로 이 문제를 푼게 잘못된건가요..? 잘 모르겠어서 질문드립니다!
답변 2
1
안녕하세요 혁준님 ㅎㅎ
DFS 탐색으로 이 문제를 푼게 잘못된건가요..? 잘 모르겠어서 질문드립니다!
-> 네 이 문제는 시간초과가 타이트한 문제이기 때문에 BFS로 풀어야 합니다. 왜 DFS로 풀면 안될까요?
while(!isFind)
{
memset(visited,0,sizeof(visited));지금 보시면 계속해서 방문배열을 초기화 -> 다시 초기정점부터 시작해서 탐색을 이어나갑니다.
즉,
a -> b
a -> b -> c
a -> b -> c -> d
이렇게 탐색을 해나가고 있기 때문에 불필요하게 중복되어 탐색하는 부분이 생겨 -> 시간초과가 뜨게 됩니다.
BFS를 이용해주셔야 합니다.
감사합니다.
감사합니다.
0
안녕하세요, 인프런 AI 인턴입니다. 장혁준님.
3-K 문제에서 DFS로 접근하셨을 때 시간초과가 발생하는 이유는 BFS가 DFS에 비해 최단 경로 탐색에 더 적합하기 때문입니다. 특히, 이 문제는 BFS가 효과적인 전형적인 예제인데요. 불과 사람 모두 내용을 최단 경로로 이동시키는 것이 중요하므로 BFS가 더 적합합니다.
참고로 다음 링크들을 통해 비슷한 질문과 해결 방법을 확인해 보실 수 있습니다:
-
- 이 답변에서는 DFS와 BFS의 차이점 및 BFS가 필요한 이유에 대해 설명합니다.
- 이 답변에서는 DFS와 BFS의 차이점 및 BFS가 필요한 이유에 대해 설명합니다.
-
- 이 답변에서는 DFS 시도 후 BFS로 전환하는 방법과 해당 문제를 해결하는 다양한 접근법에 대해 논의합니다.
- 이 답변에서는 DFS 시도 후 BFS로 전환하는 방법과 해당 문제를 해결하는 다양한 접근법에 대해 논의합니다.
DFS와 BFS 모두 그래프 탐색 알고리즘이지만, 최단 경로를 찾아야 하는 문제에서는 BFS가 적합합니다. DFS는 경우에 따라 깊이 우선으로 탐색하면서 불필요하게 많은 재귀 호출을 하게 되어 시간초과가 발생할 수 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
교안 158페이지 문의드립니다
0
11
2
코딩살구클럽 관련 건의사항
0
31
1
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
15
1
진행 방법 질문드립니다!
0
51
2
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
56
2
2주차 개념#12 트리 순회
0
26
2
백준사이트가 종료된다고 합니다.
0
287
2
백준 서비스 종료
9
890
1
sk 하이닉스 코테 대비
0
368
2
3-G 최댓값 질문
0
51
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
83
2
3-I 코드 질문드립니다.
0
62
2
3-N 질문 있습니다.
0
66
2
학습방법
0
102
2
4-H 질문 있습니다 (코드 리뷰)
0
66
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
170
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
69
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
64
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
51
2
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
0
68
2
함수별 시간복잡도
0
73
2
3-h 질문입니다.
0
49
1
안녕하세요 선생님. 시간 복잡도 4번 질문있습니다.
0
53
2
1-I 문제 질문 드립니다.
0
76
2