백준 11725_트리의 부모 찾기 문제풀이 in C++

2022년 10월 11일 in Devlog on Algorithm

1. 문제 URL
2. 문제 요구사항
3. 접근 방법
4. 풀이 순서
5. 소스코드
6. 문제 풀이 결과

문제 URL

---

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

문제 요구사항

---

• 루트 없는 트리가 주어진다.
• 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
• 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다.
• 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
• 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

접근 방법

---

• 각 노드 정보를 벡터에 담고, bfs 탐색을 통해 방문 체크 변수가 해당 노드를 방문하지 않았다면, 해당 노드의 부모 노드 값을 arr에 갱신한다.

풀이 순서

---

1. 노드 정보를 입력 받아 vector 배열 v에 저장한다
2. 루트 노드 1부터 bfs 탐색한다.
   • visited[1] = true, queue에 1을 넣고, queue가 빌 때까지 탐색
   • 현재 노드의 값을 x로 두고, queue pop, 해당 노드와 연결된 노드 벡터에서 탐색
   • 해당 연결된 노드가 방문되지 않았다면 ( visited [ next ] == false ) arr[ next ] = x, visited [ next ] = true, queue에 next 넣음
3. 이와 같은 작업 반복
4. arr 배열 2부터 N까지 차례로 출력

소스코드

---

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

vector<int> v[100001];
int arr[100001];
int N;
bool visited[100001] = { false, };
const int left = 0, parent = 1, right = 2;
void input() {
	cin >> N;

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

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

void solution() {
	visited[1] = true;
	queue<int> q;
	q.push(1);
	while (!q.empty()) {
		int x = q.front();

		q.pop();

		for (int i = 0; i < v[x].size(); i++) {
			int next = v[x][i];

			if (!visited[next]) {
				q.push(next);
				visited[next] = true;
				arr[next] = x;
			}
		}
	}
}

void output() {
	for (int i = 2; i <= N; i++) {
		cout << arr[i] << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	input();
	solution();
	output();

	return 0;
}

문제 풀이 결과

---