#11725 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

시간초과가 계속 났던 문제.

cin, cout을 scanf, printf로도 바꿔 보고

별걸 다 해봤지만 안됐던 이유는..

값을 구할 때

    for(int i=2; i<= N; i++)
    {
        bfs(i);
    }

이런 식으로 bfs를 매번 반복하려 했기 때문이었다

쓸데없이 bfs를 반복하고 이거때문에 visited(방문 여부 확인을 위한 부울 변수)도 계속 false로 초기화를 해야 했다.

        for(int i=0; i<graph[temp].size(); i++){
            if(visited[graph[temp][i]]== false){    
                visited[temp] = true;
                q.push(graph[temp][i]);
                //printf("%d %d\n",temp, graph[temp][i]);
                result[graph[temp][i]] = temp;
            }

그래서 부모 트리를 저장할 수 있는 result[100001] 배열을 만들어 주고, 해당하는 인덱스 값에 부모노드의 값을 넣었다.

temp가 현재 해당하는 노드이고, if문 내의 graph[temp][i]] 는 그의 자식노드이니까 반대로 넣어주면 된다!

 

전체 코드

#include <stdio.h>
#include <vector>
#include <queue>
#include <memory.h>
#define MAX 100001
using namespace std;

vector<int> graph[MAX];
int result[MAX];
void bfs(int start){
    int visited[MAX];
    memset(visited, false, sizeof(visited));    
    queue<int> q;
    q.push(start);
    visited[start]=true;
    while(!q.empty()){
        int temp = q.front();
        q.pop();
        for(int i=0; i<graph[temp].size(); i++){
            if(visited[graph[temp][i]]== false){    
                visited[temp] = true;
                q.push(graph[temp][i]);
                //printf("%d %d\n",temp, graph[temp][i]);
                result[graph[temp][i]] = temp;
            }
        }
    }
}
int main(){
    int N;
    scanf("%d",&N);
    int u, v;
    for(int i=0 ; i<N-1; i++){
        scanf("%d %d",&u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    bfs(1);
    for(int i=2; i<= N; i++)
    {
        printf("%d\n",result[i]);
    }
    /*for(int i=2; i<= N; i++)
    {
        bfs(i);
    }*/
    return 0;
}