[알고리즘 풀이 분석] BOJ 11725 트리의 부모 찾기
실버 2 단계의 그래프 탐색 문제 BOJ 11725 트리의 부모 찾기 풀어보았다.
BOJ 11725 트리의 부모 찾기
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입출력
[입력]
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
[출력]
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
나의 풀이
풀이 방법은 깊이 우선 탐색을 이용하는 것이다.
우선 주어지는 노드 갯수가 최대 100000 개 이기 때문에 인접 행렬을 사용하는 것은 메모리 초과가 날 것이라 생각했다. 최대 100000 개의 노드별로 인접한 노드만 저장해 두고 사용했다.
트리의 루트가 1이기 때문에 1부터 깊이 우선 탐색을 시작한다. 현재 노드를 기준으로 인접한 노드 중 방문하지 않은 노드가 있다면 방문하고 해당 과정을 재귀적으로 반복한다. 방문을 진행하면서 부모 노드를 일차원 배열에 입력 해 두도록 한다.
탐색이 끝나면 완성된 부모 노드 배열을 2부터 N 까지 출력한다.
코드
#include <iostream>
#include <vector>
using namespace std;
vector<int> adjacent[100001];
bool visited[100001];
int parent[100001];
void dfs(int cur) {
visited[cur] = true;
for (int i = 0; i < adjacent[cur].size(); ++i) {
int adj = adjacent[cur][i];
if (visited[adj]) continue;
parent[adj] = cur;
dfs(adj);
}
}
int main() {
int N;
cin>>N;
for (int i = 0; i <N-1; ++i) {
int a, b;
cin>>a>>b;
adjacent[a].push_back(b);
adjacent[b].push_back(a);
}
dfs(1);
for (int i = 2; i <=N ; ++i) {
cout<<parent[i]<<'\n';
}
return 0;
}
Author And Source
이 문제에 관하여([알고리즘 풀이 분석] BOJ 11725 트리의 부모 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@nnnyeong/알고리즘-풀이-분석-BOJ-11725-트리의-부모-찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)