[C++] 11725번 트리의 부모 찾기 - 트리, DFS

#include <iostream>
#include <vector>

#define MAX_NODE 100001

using namespace std;

vector<int> node[MAX_NODE];  //두 노드 간의 연결 표현
int mom[MAX_NODE];  //한 노드의 부모 노드 메모
int N;  //노드의 개수

void f(int no, int mo)  //node 넘버와 엄마 넘버
{
    mom[no]=mo;
    for(int i=0; i<node[no].size(); i++) {
        if(node[no][i]!=mo)
            f(node[no][i], no);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    for(int i=0; i<N; i++) {
        int u, v;  //u와 v가 연결되어 있음
        
        cin >> u >> v;
        
        node[u].push_back(v);
        node[v].push_back(u);
    }
    f(1, 0);
    
    for(int i=2; i<=N; i++)
        cout << mom[i] << '\n';

    return 0;
}

 

처음에 문제 이해한다고 꽤나 쩔쩔 맸다. 차라리 2부터 출력해달라고 적어놓기 차례대로 출력하라고 하면 도대체 저게 뭘 의미하는지 어떻게 아냐고... 직접 트리르 그려봐야 아... 그런 거구나 하고 이해하지 ㅋㅋㅋㅋㅋ

 

나는 DFS를 재귀함수로 구현했는데 다른 사람의 코드를 보니까 큐로 푸는게 더 시간이 적게 드는 것 같다. 아무래도 그럴 수밖에 없겠지. 함수를 계속 불러들이는 데는 시간이 꽤 많이 걸릴 테니까....

 

 

 

<큐로 푼 코드 - 다른 사람(문제를 풀어야 볼 수 있습니다.>

https://www.acmicpc.net/source/29329844

로그인

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.