태어난김에 세계일주 시간 초과

Question

class Solution { int answer = 0; public void dfs(int[][] countries, boolean[] visited, int balance, int count) { answer = Math.max(answer, count); for (int i = 0; i < countries.length; i++) { if (visited[i] || countries[i][1] > balance) { continue; } visited[i] = true; dfs(countries, visited, balance - countries[i][0], count+1); visited[i] = false; } } public int solution(int balance, int[][] countries) { var visited = new boolean[countries.length]; dfs(countries, visited, balance, 0); return answer; } 이렇게 결과 제출하였는데, '시간 초과'라고 계속 뜨는데, 뭐가 잘못됐는지 잘 모르겠습니다.. ㅡㅜ

communityai8509 · Answer

안녕하세요, 인프런 AI 인턴입니다. 김주현님! 김주현님의 코드에서 발생하는 &lsquo;시간 초과&rsquo; 문제는 코드의 효율성에 관련된 부분일 가능성이 큽니다. DFS는 모든 가능한 경로를 탐색하기 때문에, 경우에 따라 탐색 시간의 상한이 높아질 수 있습니다. 특히 countries 배열이 커질 경우, 탐색할 경우의 수가 기하급수적으로 증가합니다. 이를 최적화하기 위한 몇 가지 방법을 제시해 드리겠습니다: 상태 저장(State Caching) : 중복된 상태의 탐색을 피하기 위해 메모이제이션 기법을 사용할 수 있습니다. 이미 탐색한 상태를 저장하고, 동일한 상태가 나타나면 바로 결과를 반환하도록 합니다. 제한적인 탐색 : 시간이 많이 소모되는 부분을 줄이기 위해 불필요한 경로를 조기에 종료할 수 있습니다. 예를 들어, 특정 잔고 이하로는 더 이상 탐색하지 않도록 제한하여 효율성을 높일 수 있습니다. 순서 조정 : 가능하다면, countries 배열을 방문 비용의 오름차순으로 정렬하여 더 빨리 종료할 수 있는 경로를 우선적으로 탐색하는 기준을 마련합니다. 아래 URL에서 유사한 상황에 대한 해결 방법을 다룬 답변을 참조하여 추가적인 최적화 방법을 탐색할 수 있습니다: 시간초과 해결 방법 : 시간 복잡도를 줄이는 여러 방법을 다룬 댓글 부분집합 전역변수 질문 : DFS 및 순회 최적화 방법에 대한 토론 위의 조정 사항을 통해 코드의 효율성을 높일 수 있을 가능성이 큽니다. 개선된 알고리즘을 통해 문제를 해결하시기를 바랍니다. 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.