graph 채울때 for문 설계 질문

[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편

알고리즘 수업 - 깊이 우선 탐색 1 (백준 24479)

해결된 질문

작성

그 전 문제들까지는 graph를 채울 때

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

java 코딩-테스트 알고리즘 dfs

답변 2

개발자로 취직하기

지식공유자

안녕하세요 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)를 기준으로 반복하는 것입니다.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. dnrwls9115님, 동일한 주제로 발생하는 혼란에 대해 도움이 될 수 있기를 바랍니다.

질문에 대해 정리해보자면, 그래프를 채울 때 반복문을 설계하는 부분에서 조건이 < M 또는 <= N으로 사용되는 경우가 헷갈리셨던 것 같습니다. 기본적으로 반복문의 종료 조건은 문제의 의도에 따른 데이터의 특성과 구조에 따라 달라질 수 있습니다.

i < M 사용의 경우: 일반적으로 M은 간선의 개수일 때 사용되며, 그래프의 각 간선을 차례로 처리하거나 초기화하는 경우에 사용됩니다. 인덱스가 0부터 시작하므로 i < M으로 채워지게 되는 것이 이치에 맞습니다.
i <= N 사용의 경우: N은 대부분 노드(정점)의 개수를 나타내며, i <= N은 노드 번호가 1부터 시작해서 N까지 처리해야 할 때 사용됩니다. 예를 들어, 노드 개수가 5개일 경우, 노드의 인덱스를 1부터 N까지로 반복문을 설정하게 됩니다.

예제 코드를 통해 더 명확하게 이해하실 수 있도록 아래 링크들을 참조해주시면 좋겠습니다:
- 이상한게 햇갈리는데요….. - 반복문에서 N, M의 사용에 대한 설명
- 침투 (백준 13565) 문제중 질문입니당 - 그래프의 탐색에 대한 질문과 답변

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

인프런 커뮤니티 질문&답변

graph 채울때 for문 설계 질문