4-C 입력 질문 있습니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

4-C와 다양한 타입의 함수

작성

114

   for(int i = 1; i <= n; i++){
        cin >> m; 
        for(int j = 0; j < m; j++){
            cin >> temp; 
            adj[i].push_back(temp); 
            adj[temp].push_back(i); 
        } 
    }

입력을 받아서 인접 노드들을 벡터에 삽입해주셨는데, adj[temp].push_back(i); 이 부분이 들어가게 되면 같은 노드가 2번씩 벡터에 삽입되지 않나요?
예를 들어, 예제 입력 1에서 보면
1~6번 구역마다 인접 구역을 입력으로 받으니까
adj[i].push_back(temp); 이코드만 있어도 양방향 간선이 표시된다고 생각합니다.
a[1] => {2, 4}

a[2] => {1,3,6,5}

a[3] => {4, 2}

a[4] => {1, 3}

a[5] => {2}

a[6] => {2}

이렇게요

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 상민님 ㅎㅎ

adj[i].push_back(temp); 이코드만 있어도 양방향 간선이 표시된다고 생각합니다.

>> 네 맞습니다. 이문제는 그정도만으로도 충분하네요.

보통의 경우에는 양방향간선인 경우 저렇게 해주어야 하는데 이문제 같은 경우는 입력자체가 저렇게 들어와서 상민님 말씀대로 한번만 해도 괜찮습니다.

감사합니다.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다.

김상민님께서 질문하신 adj[temp].push_back(i); 구문의 목적과 관련하여, 이 부분은 양방향 그래프의 간선을 나타내기 위해 필요한 코드입니다. 즉, 각 노드가 서로를 가리킬 수 있도록 상호적으로 벡터에 추가하는 것입니다. 이를 통해 그래프의 양방향성을 표현할 수 있습니다.

김상민님의 예제 입력에 따른 결과를 보면 양방향성이 필요함을 알 수 있습니다. 예를 들어, a[1]에 {2, 4}가 있다면, a[2]와 a[4]에도 각각 1이 포함되어야 올바른 양방향 그래프를 구성할 수 있습니다. 단순히 adj[i].push_back(temp);만 사용하는 경우, 이러한 양방향성을 표현할 수 없게 됩니다.

관련 내용과 유사한 상황에 대한 질문이 이전에도 다뤄졌으니, 4-c_17471 1차원 벡터 2차원 벡터 질문과 답변을 확인하시면 도움이 될 것입니다. 이 질문에서는 벡터를 사용하여 간선 정보를 어떻게 저장하는지, 그리고 특히 양방향 그래프에서 어떻게 각 노드 간 연결을 표현하는지에 관한 설명이 포함되어 있습니다.

질문하신 내용에 대해 구체적인 설명을 원하신다면 링크된 답변에서 자세한 정보를 얻으실 수 있습니다. 이는 벡터를 사용해 인접 리스트를 구현하는 과정에서 발생할 수 있는 혼란과 관련된 질문에 대한 답변을 포함하고 있습니다.

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

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

4-C 입력 질문 있습니다.