3-k 3197 질문드립니다!

작성한 질문수 4

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가 더 적합합니다.

참고로 다음 링크들을 통해 비슷한 질문과 해결 방법을 확인해 보실 수 있습니다:

• 3 - D : 4179 질문있습니다

  • 이 답변에서는 DFS와 BFS의 차이점 및 BFS가 필요한 이유에 대해 설명합니다.
    

• 3-K 시간초과 질문 있습니다.

  • 이 답변에서는 DFS 시도 후 BFS로 전환하는 방법과 해당 문제를 해결하는 다양한 접근법에 대해 논의합니다.
    

DFS와 BFS 모두 그래프 탐색 알고리즘이지만, 최단 경로를 찾아야 하는 문제에서는 BFS가 적합합니다. DFS는 경우에 따라 깊이 우선으로 탐색하면서 불필요하게 많은 재귀 호출을 하게 되어 시간초과가 발생할 수 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.