인프런 커뮤니티 질문&답변
작성한 질문수
ch 배열의 값을 확인해서 더 이상 반복문이 돌지 않도록 하는 것도 유효한가요?
작성
·
129
·
수정됨
0
private static int solution(int v, int cost) {
int answer = 0;
Queue<Edge> pq = new PriorityQueue<>();
pq.offer(new Edge(v, cost));
while (!pq.isEmpty()) {
if (successTree()) { // 모든 노드가 트리에 추가되었을 때는 반복문을 더이상 돌지않는다.
break;
}
Edge cur = pq.poll();
if (ch[cur.v]) {
continue;
}
ch[cur.v] = true;
answer += cur.cost;
for (Edge edge : graph.get(cur.v)) {
if (!ch[edge.v]) {
pq.offer(edge);
}
}
}
return answer;
}
private static boolean successTree() {
for (boolean check : ch) {
if (!check) {
return false; // 아직 연결 안 된 노드가 있다면 false를 return
}
}
return true; // 이미 트리가 다 완성되었다면 true를 return
}
이렇게 pq를 도는 반복문에 successTree라는 메소드를 추가하여 모든 노드가(=도시) 트리에 포함되었다면 바로 true를 return 시켜 pq에 대한 반복문이 돌지 않도록 수정했습니다.
이게 코드 수행 시간에 더 효율적인 방법인지 강사님의 의견이 궁금하여 질문해봅니다!
저는 마지막 노드까지 트 에 추가되었어도 pq에 남아있는 값들이 있어 의미없는 로직을 돌 것이라고 생각해 추가하게 되었습니다만 ch 배열을 탐색하는 데에 걸리는 시간이 더 걸려 해당 로직을 수행하는 것이 더 비효율적인지 궁금합니다.
또한, 이미 노드가 다 들어가있다면 그 뒤에 pq가 반복할 일이 없어 해당 메소드가 의미가 있는지 없는지 궁금합니다. 이전에 pq에 남아있는 노드들이 poll()될 수 있다고 생각했거든요..//
항상 강의 잘 보고있습니다. 감사합니다.
답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
여니그니님의 질문에 대하여, 강의 내용과 관련하여 질문자님이 제안하신 ch 배열을 사용하여 불필요한 반복을 줄이는 방법의 효율성에 대해 의견이 제시된 유사한 경우를 찾았습니다.
강사님의 답변에서는 다양한 효율성 관련 질문에 대해 설명을 제공하시기도 하는데, 구체적으로 “원더랜드(프림) 질문입니다.”에서 인접 리스트와 우선순위 큐를 다루면서 객체를 새로 생성하여 추가하는 방법에 대해 다루고 있습니다. 이 질문은 객체 생성에 대한 비용과 기타 성능 관련 고려를 다루고 있어, ch 배열과 pq의 사용법에 대한 성능 고려 질문에 부분적인 해답을 줄 수 있을 것으로 보입니다.
또한, “숙제 코드 리뷰 부탁드립니다.” 질문에서는 graph 인접 리스트와 ch 배열을 사용하여 이미 방문한 곳을 체크하는 방법에 대해 코드 리뷰를 요청한 사례가 있습니다. 강사님은 이 구현 방식에 대해 긍정적인 피드백을 제공하셨습니다.
여기서 중요한 점은, successTree 메서드를 통해 모든 노드가 트리에 포함되었는지 확인하고, 그에 따라 추가적인 탐색을 중지하는 로직은 특정 경우에 있어서는 성능 향상에 기여할 수 있음을 시사합니다. 하지만, 이 방법이 코드의 전반적인 수행 시간에 어떤 영향을 미칠지는 자료 구조 및 처리해야 할 데이터의 크기와 복잡도에 따라 달라질 수 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.