인프런 커뮤니티 질문&답변
작성한 질문수
완탐 3-E 시간초과 관련 질문입니다.
해결된 질문
작성
·
73
·
수정됨
0
https://www.acmicpc.net/source/93603480
메모리 초과 날 수 있는 게 아무래도 정점을 6개씩 계속해서 넣다 보니까 queue에서 나는 거 같은데.. 막상 큰돌님 코드와도 큰 차이가 없는 거 같고.. 어떤 부분이 잘못돼서 메모리 초과가 났는지 궁금해요.
답변 2
1
안녕하세요 병욱님 ㅎㅎ
이 코드는 방문된 정점을 재방문하는 코드입니다.
if(visited[nv.a][nv.b][nv.c] == 1) continue;
visited[nv.a][nv.b][nv.c] = visited[v.a][v.b][v.c] + 1;
q.push(nv);그렇기 떄문에 한정점당 6번 더 방문을 할 수 있는 코드이기 때문에 비효율적입니다.
예를 들어 탐색해야 하는 정점이 20개라면
6^20이 되버립니다. 6^20은 3,656,158,440,062,976 이나 되는 숫자입니다.
방문한 정점은 재방문하지 않게 다시 짜보시겠어요?
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
1
안녕하세요, 인프런 AI 인턴입니다. 유병욱님.
3-E 완전 탐색 문제에서 시간 초과가 발생하는 주된 이유는 불필요한 연산이나 큐에 중복으로 데이터를 넣는 부분 때문일 가능성이 높습니다. 큐에 데이터를 넣는 로직에서 중복된 연산이 발생하거나 탐색 공간이 비효율적으로 관리되는 경우, 시간이 많이 소모될 수 있습니다.
큐 관리 효율성: 큐에 데이터를 넣는 로직을 상세히 살펴보세요. 큐가 불필요하게 커지지 않도록 중복된 정점이나 이미 방문한 정점은 체크하여 다시 넣는 것을 방지해야 합니다.
방문 체크: 각 정점을 방문할 때마다 방문 여부를 적절히 체크하고 중복 방문을 방지하세요. BFS나 DFS에서 방문 처리 로직은 시간 초과를 방지하는 중요한 요소입니다.
시간 복잡도 분석: 전체 탐색의 시간 복잡도를 다시 한 번 계산해 보세요. 특별히, 큰 입력에 대해 얼마나 자주 연산이 수행되는지 점검해 보세요. 만약 시간 복잡도가 너무 큰 경우, 알고리즘 자체를 개선할 필요가 있습니다.
관련 질문과 답변에서 시간 초과 문제를 해결하는 다양한 방법 및 최적화할 수 있는 부분들에 대한 힌트를 찾아보실 수 있습니다:
- “3-K 질문있습니다.!” - 비슷한 문제에서 BFS 및 메모리 사용 최적화에 대한 강사님의 상세 설명을 참고하세요.
- “3-H 시간초과” - 효율적인 큐 관리와 부모 저장을 통한 경로 추적 방법에 대한 설명이 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
위 코드가 ==1일때 만 넘어가는 로직이라 거리 정보가 들어간 visited에선 의미가 없어서 그런거네요. 평소엔 그렇게 안 짰는데 왜그랬을까요..; ㅎㅎ 감사합니다. 확실히 시간이 지나고 멀리서 보니까 이상한 짓 한 걸 알겠네요. 종종 여쭤보겠습니다 바쁘실텐데 감사해요!