3-J 풀이 방법에 관한 질문입니다!

작성한 질문수 16

0

안녕하세요 ㅎㅎ

		fill(&visited[0][0], &visited[0][0] + 304 *304, 0);
		dfs(y1-1,x1-1); 

이렇게 계속해서 초기화를 하고 -> dfs 하는 것은 괜찮습니다.

로직상 문제되는 부분도 없이 잘 구축하셨구요 ㅎㅎ

다만, 이러한 비효율적인 부분이 발생합니다.

a -> b

a -> b -> c

a -> b -> c -> d

이렇게 불필요한 정점탐색이 일어나게 되는 것이죠.

또한 큐를 이용한 풀이와 제가 작성한 풀이 중 다시 풀게 되면 어떤 방식으로 풀이를 해야할지 고민이 됩니다!

=>

간단한 문제는 앞의 코드처럼 어느정도는 불필요한 탐색이 있더라도 이렇게 푸시구요. 만약 시간초과가 나면 제가 만든 큐 이용해서 하는 풀이로 하는게 좋을 것 같습니다.

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

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

감사합니다.

강사 큰돌 올림.

0

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

주난의 난 문제를 다양한 방법으로 해결할 수 있다는 점에서 여러분의 접근방식이 참신하고 좋습니다. 큐를 사용하지 않은 방법도 문제에서 요구하는 조건을 만족했다면 충분히 유효한 풀이라고 생각합니다.

큐와 BFS 사용 장점:
큐를 활용한 BFS는 그래프 관련 문제에서 최단 경로를 찾거나 맵 탐색에 있어서 효율적인 방법입니다. BFS는 탐색을 레벨 단위로 진행하기 때문에 최단 경로를 보장할 수 있다는 이점이 있습니다.

현재 사용한 방법과 큐의 비교:
1. 큐를 사용하지 않는 방법: 만약 문제의 크기와 복잡도가 상대적으로 낮고 탐색의 최적 경로가 필수적이지 않은 경우, 지금처럼 큐를 사용하지 않고 구현하신 솔루션이 작동할 수 있습니다. 하지만, 제한된 테스트 사례에서만 유효할 수 있어 복잡한 경우 오류가 날 수 있습니다.

2. 큐를 사용한 방법: 큐를 이용해 BFS를 구현하게 되면, 각 노드(또는 셀)를 방문하는 순서가 명확해지고, 이미 방문한 노드들을 추적하여 불필요한 연산을 줄일 수 있습니다. 특히, 경로의 가중치나 여러 출발점에서의 합리적인 도착을 요구하는 문제에서는 BFS가 탁월합니다.
   

다시 이 문제를 푸는데 어떤 방식을 선택할지는 문제의 성격과 효율성 요구 사항에 따라 달라질 수 있습니다. BFS는 많은 경우에 필수적이지만, 문제 풀이에서 여러분이 이해하고 구현하기 쉽고, 잘 작동한다면 현재 방법을 사용하셔도 무방합니다.

관련 질문 답변 예시로 다음을 참고하시면 도움이 될 것입니다.
- 3-J 문제의 큐를 활용한 BFS에 대한 문의 - BFS를 효과적으로 사용하는 방법에 대한 토론이 포함되어 있습니다.

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