인프런 커뮤니티 질문&답변
작성한 질문수
3-K 질문
해결된 질문
작성
·
11
0
큰 돌 선생님 안녕하세요.
항상 명강의 잘 듣고 있습니다. (_ _)
다름이 아니라 약간 큰 돌쌤을 빙의해서 문제들을 먼저 풀고 > 해결을 보면서 차근차근 나아가고 있는데요.
다름이 아니라 3197 백조의 호수
2개의 Queue 로 푸는 건 인지했습니다.
그런데 시간 초과가 발생해서요.
코드 링크 http://boj.kr/23d82bb7e38c40b094f71a83b76d7e19
제가 예상하는 부분은 check() 메서드에서
fill(&visited2[0][0], &visited2[0][0] + (SIZE - 1) * (SIZE - 1), 0);
이 부분이 시간 초과에 영향이 큰 것 같은데 맞을까요?
문제는 이제 틀리더라도 맞는 방향으로 나아가는 것 같은데, 항상 문제를 풀고 나면 시간 계산을 할 때 어렵네요.
바쁘지 않으실 때 확인 부탁드립니다.
감사합니다.
답변 2
0
안녕하세요 도현님 ㅎㅎ
네 맞습니다.
사실 저 배열 초기화는 시간에 영향을 미치지는 않지만...
그 다음이 문제입니다.
백조의 처음 위치부터 다시 전체 맵 탐색
-> 다시...
-> 다시...
이 과정이 반복되기 때문에 시간초과가 나게 됩니다.
이부분을 탐색이 완료된 지점부터 다시 탐색 -> 으로 바꿔주셔야 합니다.
문제는 이제 틀리더라도 맞는 방향으로 나아가는 것 같은데, 항상 문제를 풀고 나면 시간 계산을 할 때 어렵네요.
-> 이제 로직은 맞고 비효율적인 것을 효율적으로 바꾸는 과정만 남았다고 생각하시면 됩니다. 너무 좋습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다. 김도현님.
3197 백조의 호수 문제는 BFS를 활용하여 얼음을 녹이고 두 백조가 만나는 시점을 찾는 문제로, 효율적인 시간 복잡도 관리를 필요로 합니다. 기존에 시간 초과 문제와 관련하여 많은 수강생 분들이 비슷한 문제를 경험하셨고 이에 대한 답변이 많이 남겨져 있습니다.
우선, fill(&visited2[0][0], &visited2[0][0] + (SIZE - 1) * (SIZE - 1), 0); 부분은 visited2 배열을 매번 초기화하는 과정에서 시간이 많이 소요될 수 있습니다. 불필요한 초기화를 줄이려면, 방문 여부를 트래킹할 때 초기화 없이 매번 사용하는 다른 방법으로 ‘방문 횟수’를 기록하거나 ‘변형된 방식의 visited 배열’을 사용하는 방법도 고려해보실 수 있습니다. 더 구체적으로, ‘visited’ 배열에 저장하는 값을 시간 단계별로 나눠 저장하면 배열 초기화를 최소화할 수 있습니다.
이와 관련된 추가적인 최적화와 방법을 참고할 수 있는 좋은 질문과 답변이 있습니다:
- 3-K 코드 질문있습니다
위 답변들에서는 BFS의 효율성을 높이기 위한 여러 가지 테크닉과 접근 방법에 대해 다루고 있으며, 이를 통해 비슷한 문제들을 풀 때 더욱 효율적으로 접근하는 방법을 배우실 수 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.