백준 11725 (트리, DFS)

11725번: 트리의 부모 찾기

과정

• 대놓고 트리라고 하니까.. 그냥 DFS로 작성했다. 부모만 찾으면 되는 문제라 간단하지만;;
• vector선언과 메모리크기를 초기화하는 과정에서 vector와 array의 차이를 잘 모르고 있었던 것 같다.
• 나는 지금까지 왠만하면 vector의 크기를 MAX로 미리 고정하지 않고 resize를 통해 정해줬다. (그게 메모리적으로 이득이니까)
• 근데 이번 문제는 vector의 장점을 이용해서 하나의 index안에 여러값을 push_back 해야한다. 근데 이럴 경우, 선언 자체를 메모리값이 0인채로 해서 그런지 오류가 발생한다. 이때 벡터의 선언에서 소괄호, 대괄호의 차이를 알고 있어야 한다.

C++ vector 선언에서 중괄호, 대괄호 차이.

쉽게 말해

vector<int> Node[100001]

 

• 이건 100001만큼의 메모리를 가진 배열의 각 인덱스 한칸이 벡터가 되는 것이다. 

vector<int> Node(100001)

• 그리고 이건 100001만큼의 메모리를 가진 벡터를 선언한 것이다.

이 둘의 차이는 1번은 2차원 벡터(배열)형태, 2번은 1차원 벡터라는 점이다.

(물론 1번은 1차원 배열안에 2차원 벡터가 있는 꼴이므로 이걸 2차원 벡터라고 부르긴..좀 뭐할지도?)

그래서 내가 필요한건 2차원 모양이므로 1번을 사용했다.

 

코드

#include <iostream>

#include <vector>

using namespace std;

int N = 0;                  // 노드의 개수

vector<int> Node[100001];   // 노드의 부모

bool visited[100001];       // 방문 여부

int parentNode[100001];     // 부모 노드

void DFS(int num)

{

    visited[num] = true;

    for(int i = 0; i < Node[num].size(); i++)

    {

        int next = Node[num][i];

        if (visited[next] == false)

        {

            // 부모노드는 지금 num에 해당하는 숫자

            // next는 num과 연결된 노드이기 때문

            parentNode[next] = num;

            DFS(next);

        }

    }

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(nullptr); cout.tie(nullptr);

    cin >> N;

    for (int i = 2; i < N+1; i++)

    {

        int node1, node2;

        cin >> node1 >> node2;

        Node[node1].push_back(node2);

        Node[node2].push_back(node1);

    }

    // 루트 노드를 1로 설정함

    DFS(1);

    for (int i = 2; i < N+1; i++)

    {

        cout << parentNode[i] << "\n";

    }

    return 0;

}

 

추가적으로 VS에서는 잘 돌아가긴 하는데 백준에서는 이런 오류가 발생했다. 

이건 고친 코드이지만, 이전에는 DFS함수의 반환형이 있었는데, 보는거와 같이 DFS함수는 반환할 값이 없다.

따라서 WithoutReturning이라는 오류가 발생할 수 있다.