잠겨버린 사물함 시간초과 관련 질문입니다.

Question

class Solution { public int solution(int[][] lockers) { int answer = -1; int n = lockers.length; boolean[] visited = new boolean[n]; visited[cur] = true; dfs(visited, 0, lockers); for(boolean isVisit : visited) { if (isVisit) { answer++; } } return answer; } void dfs(boolean[] visited, int cur, int[][] lockers) { for(int nxt : lockers[cur]) { if(!visited[nxt]) { visited[nxt] = true; dfs(visited, nxt, lockers); } } } } 위와 같이 풀어봤는데 문제풀이 사이트에서 시간 초과가 납니다 ㅠ 어떻게 해야 시간초과가 나지 않을까요

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. ss5love님. DFS(깊이 우선 탐색)를 사용하셨네요. 주어진 코드에서 시간 초과가 발생하는 이유는 DFS 호출이 백트래킹 없이 무제한으로 깊게 들어갈 수 있는 구조이기 때문일 수 있습니다. 하지만 java로 제공된 코드에서는 DFS에서 시간 초과가 나지 않아야 합니다. 시간 초과 발생 시 몇 가지 점검해야 할 부분을 안내드립니다. 무한 루프 검사 : DFS 호출 시 인접 리스트(또는 배열)에서 순환 구조가 있는지 확인합니다. 이미 방문한 노드를 다시 방문하지 않도록 visited 배열을 올바르게 활용하신 점은 잘 하셨습니다. 데이터 구조 최적화 : 사용 중인 자료 구조가 적절한지 확인하세요. Java에서는 기본적으로 배열을 사용한 boolean[] 를 사용해 visited 배열을 관리하고 있어 효율적입니다. 인접 리스트 구성 확인 : 주어진 lockers 배열의 크기와 내부 리스트의 크기가 지나치게 커질 경우, 탐색 과정에서 시간이 오래 걸릴 수 있습니다. 데이터 입력 범위와 구조를 다시 한 번 확인해 주세요. 메서드 호출 최적화 : 재귀 호출의 깊이가 너무 깊지 않도록 주의해야 합니다. Java에서 기본적으로 큰 호출 스택을 사용할 수 있지만, 지나치게 깊이 들어가지 않도록 하는 것이 좋습니다. 유사 질문 및 추가 리소스: 잠겨버린 사물함 문제와 유사한 문제에 대한 모든 노드를 방문하는 DFS나 BFS에 관한 추가 자료들을 살펴보실 수 있는 것이 도움이 될 수 있습니다: DFS/BFS : BFS와 DFS의 기본 개념을 이해하는데 도움을 주는 자료입니다. 코딩 테스트에서의 시간초과 문제 해결 : 시간 초과 문제를 해결하기 위한 여러 가지 접근 방식과 최적화 방법을 제시합니다. 추가적으로 이상 없을지 주신 코드의 테스트 케이스를 유효성 있게 반복 실행 해보시기를 권장합니다. 그래도 문제를 해결하지 못하셨다면, 강의 페이지나 관련 커뮤니티에서 더 구체적인 코드 리뷰를 요청해보세요. 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.