인프런 커뮤니티 질문&답변
작성한 질문수
선생님, DFS 설명 예시 코드에서 n의 크기에 대해 질문이 있습니다!
해결된 질문
작성
·
230
0
안녕하세요 선생님! 4분33초부터 시작하는 DFS 예시 코드에 관련해서 질문이 있습니다.
선생님이 보여주신 그래프를 보면 노드의 개수가 총 5개인데 n의 크기를 보면 6이라고 되어 있네요.
처음에는 2와 4가 양방향으로 연결돼 있기 때문에 그런가 싶었는데 
이걸 인접리스트로 표현하는 코드에선 n을 4로 하셔서 뭔가 제가 잘못 생각하고 있는가 싶어서 질문드립니다.
n의 크기를 노드 개수대로 5로 수정해서 코드를 돌려보면 3번 노드를 탐색을 안 하는 걸 보면 n이 6이 돼야 할 거 같은데 왜 6이 되는지 이해가 잘 가지 않습니다 ㅠ
답변 1
0
안녕하세요 빛과소금님 ㅎㅎ
선생님이 보여주신 그래프를 보면 노드의 개수가 총 5개인데 n의 크기를 보면 6이라고 되어 있네요.
>>
지금 보시는 것처럼 1 ~ 5의 정점을 담고 있는 인접리스트입니다.
그렇다면
vector<int> adj[6]이 필요합니다.
배열의 요소는 0부터 시작합니다.
만약 n = 6이라면
즉, 0, 1, 2, 3, 4, 5의 영역, 6개를 만들게 되는 것이구..
그래서 6이 되는 것입니다. ㅎㅎ
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
그렇다면 노드의 번호가 5번이라면 adj[5] 이렇게 표현을 해야될텐데 vector<int> adj[5] 이렇게 표현하면 인덱스를 0 ~ 4까지만 사용할 수 있으니 5번 노드의 인접 리스트를 표현할 수 없어서 vector<int> adj[6] 이렇게 선언하는 것이 맞을까요?
>> 네 맞습니다. 6까지 선언하면 0 ~ 5까지 가능합니다.
처음에 제가 헷갈렸던 건 adj[n]에서 n에는 노드의 개수가 들어간다고 생각했는데 그것 때문에 지금 이런 혼란이 생긴 것 같습니다.
>> 노드의 번호가 n일 때 adj[n + 1]로 해야된다고 이해하시면 됩니다.
혹시 제가 이해한 것이 맞을까요? 질문이 너무 초보적인데 잦아서 조금 죄송하네요 ㅠ
>> 네 이해 잘하셨습니다. ㅎㅎ 모르는게 있으면 모르는 것보다 질문하시는게 좋습니다. ㅎㅎ 질문주세요.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
제가 좀 더 구글링 해보고 해 본 생각이 맞는가 해서 다시 질문 드려봅니다!
adj[idx]에서 idx는 각 노드의 번호를 의미하는 것으로 저는 이해했습니다. 1번 노드의 인접 리스트를 표현하기 위해선 adj[1] 이런 식으로요.
그렇다면 노드의 번호가 5번이라면 adj[5] 이렇게 표현을 해야될텐데 vector<int> adj[5] 이렇게 표현하면 인덱스를 0 ~ 4까지만 사용할 수 있으니 5번 노드의 인접 리스트를 표현할 수 없어서 vector<int> adj[6] 이렇게 선언하는 것이 맞을까요?
이렇게 생각하면 제가 처음 질문에서 헷갈렸던 것도 조금 해결이 되는 것 같은데요. 처음 질문에서 선생님의 교재에 나와있는 그래프는 노드 번호가 0번부터 시작하니까 vector<int> adj[4] 이렇게 선언해도 인덱스가 0 ~ 3 까지 있으니 마지막 노드 번호인 3번의 인접 리스트를 표현할 수 있어서 vector<int> adj[4] 선언을 한 것이라고 제가 이해를 해 봤습니다.
처음에 제가 헷갈렸던 건 adj[n]에서 n에는 노드의 개수가 들어간다고 생각했는데 그것 때문에 지금 이런 혼란이 생긴 것 같습니다.
혹시 제가 이해한 것이 맞을까요? 질문이 너무 초보적인데 잦아서 조금 죄송하네요 ㅠ