티스토리 뷰
728x90
https://www.acmicpc.net/problem/11725
C++ 트리
트리의 정석
부모 자식 관계가 안알려진 간선 만 주어지고 각 노드의 부모를 출력하는 문제
접근방법
트리의 정석으로 풀이했다. vector로 인접리스트 사용했고 무방향그래프로 정의했고
루트노드인 1번 노드부터 BFS탐색하면서 자식 노드의 부모노드 정보를 parents배열에 저장했다.
오답노트
visit배열을 메인함수에서 선언해줘서 초기화를 안해줬다. 그랬더니 값이 true인 경우가 있었나보다. 전역변수로 빼줬더니 해결
소스코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool visit[100001];
int main(){
int n;
cin >> n;
vector<vector<int>> adj(n+1);
queue<int> q;
int parents[n+1];
for(int i = 0 ; i < n-1 ; i++){
int a,b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
q.push(1);
visit[1] = true;
parents[1] = 0;
while(!q.empty()){
int parent = q.front();
q.pop();
for(int i = 0 ; i < adj[parent].size() ; i++){
int child = adj[parent][i];
if(!visit[child]){
visit[child] = true;
q.push(child);
parents[child] = parent;
}
}
}
for(int i = 2 ; i <= n ; i++){
cout << parents[i] << "\n";
}
return 0;
}
728x90
'알고리즘 문제풀이' 카테고리의 다른 글
[백준 5639] 알고리즘 125일차 : 이진 검색 트리 (0) | 2021.08.24 |
---|---|
[백준 1991] 알고리즘 124일차 : 트리 순회 (0) | 2021.08.23 |
[SWEA 2948] 알고리즘 122일차 : 문자열 교집합 (0) | 2021.08.17 |
[SWEA 1257] 알고리즘 11^2일차 : K번째 문자열 (0) | 2021.08.13 |
[SWEA 1256] 알고리즘 120일차 : K번째 접미사 (0) | 2021.08.12 |
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 브루트포스
- 다이나믹프로그래밍
- 백준
- 최소힙
- 백트래킹
- 알고리즘
- 프로그래머스
- 게임이론
- c++
- 스택
- 파이썬
- 그리디알고리즘
- 수학
- 토마토
- 동적계획법
- 최대힙
- 정렬
- BFS
- 투포인터
- 가장 큰 수 프로그래머스
- 이분탐색
- dp
- dfs
- 트리
- 가장 큰 수 Swift
- Swift
- 최단경로
- 우선순위큐
- 웹크롤링
- 자바
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
글 보관함