인프런 커뮤니티 질문&답변

안녕하세요 유태님 ㅎㅎ

완탐을 사용하시면서 visited배열의 가중치를 증가시키시더라구요.

>>

		visited[ny][nx] = visited[y][x] + 1; 
		ret += go(ny, nx);
		visited[ny][nx] = 0;

이부분은 모든 경우의 수를 탐색하면서 해당 경우의 수에서의 최단거리를 저장하고 -> 그걸 기반으로 거리가 k인 것을 찾아내기 위함입니다.

1. visited배열의 가중치를 증가시키려면 BFS를 사용
   >> 그게 아니라 가중치가 같은 그래프내에서 최단거리 -> BFS 사용 이라고 보시면 됩니다. DFS에서도 visited를 증가시킬 수 있습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

안녕하세요, 인프런 AI 인턴입니다.

한유태님의 질문에 대해 “DFS와 BFS의 활용 및 선택 기준”에 관한 기존 답변 링크를 추천해드립니다. 질문하신 내용에서 완전탐색(DFS)과 가중치 증가에 따른 BFS 사용에 대한 혼동이 있으신 것 같습니다. 특히, 완탐을 사용하면서 visited 배열의 가중치를 어떻게 증가시킬 수 있는지에 대한 부분이 헷갈리시는 것으로 보입니다.

다음은 관련된 내용을 다루는 기존 답변입니다:

• 3 - D : 4179 질문있습니다
  
  • 이 답변에서는 DFS와 BFS의 차이점을 설명하며 특정 문제들(예: 최단거리를 찾는 문제)에서 BFS를 선호하는 이유를 설명합니다. 그러나 가중치가 같은 그래프 내에서 BFS를 최단거리 알고리즘으로 사용할 수 있다는 점에 초점을 두고 있으며, 답변은 DFS로는 문제를 풀기 어려운 이유를 설명하고 있습니다.
    

질문하신 내용에 대해 직접적으로 해결할 수 있는 답변이나 선생님이 제공하는 구체적인 팁을 명확하게 제공하는 링크를 찾지 못했습니다. 한유태님께서 언급하신 완전탐색과 가중치 증가라는 개념을 함께 사용하면서 생기는 혼란에 대해, 선택한 알고리즘에 따라 접근법과 구현 방식이 달라질 수 있다는 것을 이해하는 것이 중요합니다. 다만, 일반적으로 가중치가 존재하고 최단 경로를 찾아야 하는 경우 BFS가 자주 사용되는 것은 사실입니다. DFS는 경로의 모든 가능성을 탐색하지만, BFS는 시작점에서부터 가까운 노드들을 순차적으로 탐색하기 때문에 레벨(또는 깊이)별로 탐색이 이루어집니다. 이러한 차이점을 기반으로 문제의 성격에 맞춰 적절한 알고리즘을 선택하는 것이 중요합니다.

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