-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
섹션7 그래프 최단거리 질문 있습니다.
23.10.16 14:28 작성 조회수 202
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.섹션 7 마지막문제 그래프최단거리의 BFS함수 내부에서 dis[v]를 0으로 다시 초기화해주는 이유가 궁금합니다. 0으로 초기화해주지 않아도 배열을 선언하고 처음 초기화할때 0으로 자동 초기화가 일어나지 않나요?
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.섹션 7 마지막문제 그래프최단거리의 BFS함수 내부에서 dis[v]를 0으로 다시 초기화해주는 이유가 궁금합니다. 0으로 초기화해주지 않아도 배열을 선언하고 처음 초기화할때 0으로 자동 초기화가 일어나지 않나요?
public static void BFS(int v){
Queue<Integer> queue = new LinkedList<>();
ch[v] = 1;
dis[v] = 0; //왜??
queue.add(v);
while (!queue.isEmpty()){
int currV = queue.poll();
for (Integer nextV : graph.get(currV)) {
if(ch[nextV]==0){ //방문한 적이 없는지 확인
ch[nextV] = 1;
queue.add(nextV);
dis[nextV] = dis[currV]+1;
}
}
}
}
답변을 작성해보세요.
0
인프런 AI 인턴
2023.10.18
안녕하세요 jia5232 님, 인프런 AI 인턴이에요.
dis[v]를 0으로 다시 초기화해주는 이유는 해당 문제에서 그래프의 최단거리를 구하는 과정에서 dis 배열을 사용하기 때문입니다. BFS 알고리즘을 이용하여 최단거리를 구할 때, 시작점에서 다른 노드까지의 거리를 dis 배열에 저장하는데, 처음에는 시작점에서 갈 수 있는 노드까지의 거리를 갱신하고자 dis 배열을 초기화해야 합니다.
배열은 선언이 되면 자동으로 0으로 초기화되지만, 배열의 일부분만 초기화해주고 싶을 때는 해당 부분만 별도로 초기화해주어야 합니다. 따라서 dis 배열의 일부를 0으로 초기화하기 위해 dis[v] = 0;와 같은 코드를 작성하는 것입니다.
이렇게 초기화를 해주는 이유는, 최단거리를 구하는 과정에서 각 노드에 대한 최단거리를 구하기 위해 초기값이 필요하기 때문입니다.
다른 질문이 있으시면 언제든지 물어보세요! 감사합니다.
답변 1