인프런 커뮤니티 질문&답변
작성한 질문수
3-k 백조문제 질문
해결된 질문
작성
·
27
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
안녕하세요! 백조문제 강의보기 전에 제 방법으로 나름 풀어보았는데요,
케이스들은 다 맞는데 시간초과가 나서 질문드립니다.
어디가 잘못된것인지 알 수 있을까요?
https://www.acmicpc.net/source/95674502
감사합니다!
답변 2
0
안녕하세요 토끼님 ㅎㅎ
//백조 만나나 확인하기
int bird_dfs(int y, int x){
memset(visited, 0, sizeof(visited));
visited[y][x] = 1; 이부분이 조금 비효율적인 것 같습니다.
백조가 만나나를 확인하려면 매번 초기화를 해서 다시 시작해서 -> 확인해야 합니다.
즉,
a -> b
a -> b -> c
a -> b -> c -> d
이렇게 불필요한 경로가 반복되는 것이죠.
해당 부분을 방문한지점부터 시작하는 BFS 로 바꿔보시겠어요?
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다. 북치는토끼님.
백조 문제에서 시간 초과가 발생한 경우는 대개 알고리즘의 시간 복잡도가 문제의 모든 데이터를 처리하기에 충분하지 않을 때 발생합니다. 기존 강의의 질문 게시판을 참고하시면 비슷한 질문들이 많이 있습니다. 유사한 사례에 대한 해결책을 제공하는 기존 답변을 소개합니다.
입출력 최적화 및 BFS 활용: 이 문제는 보통 BFS를 사용하여 효율적으로 풀 수 있습니다. 입력과 출력 부분도 최적화가 필요할 수 있습니다. 비슷한 사례를 살펴보시려면 시간초과와 입출력 최적화 관련 질문 게시물을 참고하세요.
BFS와 DFS 조합: 두 알고리즘을 적절히 조합하여 문제를 효율적으로 해결할 수 있는 전략도 있습니다. BFS, DFS 예제 및 코드 최적화 방법을 참조하면 도움이 될 것입니다.
알고리즘 최적화: 알고리즘의 시간 복잡도를 분석하고, 탐색 공간을 줄이기 위한 최적화가 필요할 수 있습니다. BFS로 얼음을 녹이는 로직을 최적화하면 시간 초과를 해결할 수 있습니다.
코드의 수정을 위해 위의 관련 설명을 기반으로 코드의 구조나 알고리즘의 접근 방식을 다시 한 번 점검해 보시길 추천드립니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.