graph 채울때 for문 설계 질문

Question

그 전 문제들까지는 graph를 채울 때 조건문에서 i < M으로 간선의 개수로 했는데 왜 이번문제에서는 i <=N으로 하나요? 전에 2차원 배열을 가득 채우고 할 때 i<=N은 dfs 함수에서 사용했었는데..이해를 못하겠스빈다

gaebaljob · Answer

안녕하세요 dnrwls91152585님 :) 두 for문은 역할이 완전히 다릅니다. 하나는 그래프의 '틀'을 만드는 초기화용이고, 다른 하나는 그 틀에 간선 '내용'을 채우는 용도입니다. for (int i = 1; i <= N; i++) 루프의 역할 이 코드는 정점의 개수(N)만큼 반복하면서, 각 정점에 연결될 간선들을 저장할 빈 ArrayList 를 만들어주는 역할을 합니다. graph = new ArrayList[MAX] 라고 선언만 하면 graph 의 각 칸은 비어있는 상태( null )라서, 이 과정을 거치지 않고 graph[i].add() 를 호출하면 오류가 납니다. 즉, N 개의 정점 각각에 대해 "이제부터 여기에 간선을 저장할 수 있어"라고 준비시켜주는 단계입니다. 문제에서 노드의 번호를 0 ~ N-1이 아닌 1 ~ N까지로 정의했기 때문에 1 부터 N을 포함한 지점까지 반복하도록 정의했습니다. for (int i = 0; i < M; i++) 루프의 역할 이 코드는 간선의 개수(M)만큼 반복하면서, 입력으로 주어진 간선 정보를 읽어옵니다. u v 를 읽어서, 위 1번 과정에서 만들어 둔 graph[u] 리스트에 v 를 추가하고, graph[v] 리스트에 u 를 추가하는 일을 합니다. 미리 준비된 공간에 실제 데이터를 채워 넣는 단계라고 보시면 됩니다. 요약하자면, 첫 번째 N번 반복하는 루프는 N 개의 빈 서랍(리스트)을 만드는 작업이고, 두 번째 M번 반복하는 루프는 M 개의 서류(간선)를 해당 서랍에 넣는 작업이라고 생각하시면 쉽습니다. 그래서 하나는 정점 수(N)를 기준으로, 다른 하나는 간선 수(M)를 기준으로 반복하는 것입니다.

communityai8509 · Answer

안녕하세요, 인프런 AI 인턴입니다. dnrwls9115님, 동일한 주제로 발생하는 혼란에 대해 도움이 될 수 있기를 바랍니다. 질문에 대해 정리해보자면, 그래프를 채울 때 반복문을 설계하는 부분에서 조건이 < M 또는 <= N 으로 사용되는 경우가 헷갈리셨던 것 같습니다. 기본적으로 반복문의 종료 조건은 문제의 의도에 따른 데이터의 특성과 구조에 따라 달라질 수 있습니다. i < M 사용의 경우 : 일반적으로 M 은 간선의 개수일 때 사용되며, 그래프의 각 간선을 차례로 처리하거나 초기화하는 경우에 사용됩니다. 인덱스가 0부터 시작하므로 i < M 으로 채워지게 되는 것이 이치에 맞습니다. i <= N 사용의 경우 : N 은 대부분 노드(정점)의 개수를 나타내며, i <= N 은 노드 번호가 1부터 시작해서 N까지 처리해야 할 때 사용됩니다. 예를 들어, 노드 개수가 5개일 경우, 노드의 인덱스를 1부터 N까지로 반복문을 설정하게 됩니다. 예제 코드를 통해 더 명확하게 이해하실 수 있도록 아래 링크들을 참조해주시면 좋겠습니다: - 이상한게 햇갈리는데요&hellip;.. - 반복문에서 N, M의 사용에 대한 설명 - 침투 (백준 13565) 문제중 질문입니당 - 그래프의 탐색에 대한 질문과 답변 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.