목록트리 (13)

1일1알

백준 11725번 트리의 부모 찾기 C++

그래프, 트리 관련 문제이다. 우선 (n+1)*(n+1) 행렬을 만들어서 트리를 인접 행렬을 통해 나타내는 방식을 생각해볼 수 있다. 노드가 양방향으로 연결되어있기 때문에 (1,6)을 받으면 (1,6)과 (6,1) 모두 저장한다. 하지만 이런 방식으로 풀면 비어있는 공간도 모두 탐색하면서 시간이 오래 걸려 시간 초과가 날 것 같아서 다른 방법을 생각해보았다. 2차원 벡터를 사용하여 노드와 연결된 노드만 저장하는 방식이다. vector[1] : 4, 6 vector[2] : 4 .... 이런식으로 만들었다. 우선 루트가 1이라고 했으니 큐에 1을 넣고 시작한 뒤 노드 r을 1로 저장하고 pop을 한번 해준다. 그리고 vector[r] 을 탐색하면서 원소가 아직 방문이 되지 않았을 경우에 해당 원소를 큐에 ..
알고리즘 2021. 10. 17. 12:39
이전 Prev 1 2 3 Next 다음