백준 11725번, 트리의 부모 찾기

백준 11725번 c++ 문제풀이

문제:

백준 11725

풀이:

1. vector에 정점간의 연결 정보를 모두 저장한다.
2. 깊이 우선 탐색을 하기 위해 정점의 방문 여부를 bool visited에 저장하고, 재귀를 통해 방문하지 않은 곳을 탐색한다.
3. 위 과정을 진행할 때, 현재 노드의 부모 노드는 하나이고 이미 방문했을 것이기에 현재 노드의 연결된 노드 중 if(visited)이면 그 노드는 부모 노드일 수밖에 없다. 그 값을 배열에 저장해주고 출력한다.

코드:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int ans[100000];

void dfs(vector<int> v[], bool visited[], int start){//깊이 우선 탐색
    
    visited[start] = true; //방문한 노드 방문 처리.

    for(int i=0;i<v[start].size();i++){//현재 노드와 연결된 모든 노드 방문 여부 확인하기
        if(!visited[v[start][i]]){//방문하지 않은 노드는 자식 노드이므로 탐색진행
            dfs(v, visited, v[start][i]);
        }
        else if(visited[v[start][i]]){//이미 방문한 노드는 부모 노드이므로 저장
            ans[start] = v[start][i];
        }
    }

}

int main(){

    int n;

    cin >> n;

    vector<int> v[n+1];

    for(int i=0;i<n-1;i++){
        int a, b;

        cin >> a >> b;

        v[a].push_back(b);
        v[b].push_back(a);
    }

    bool visited[n+1] = {0,};

    dfs(v, visited, 1);

    for(int i=2;i<=n;i++){
        cout << ans[i]<<"\n";
    }

    return 0;
}

약간 응용력 문제인거 같았다.

감사합니다.