티스토리 뷰
링크 : www.acmicpc.net/problem/11725
문제요약
입력 : N, 각각 연결된 노드들
출력 : N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력
코드작성개요
필요한 변수
N - 받을 노드의 줄
a, b - 연결된 노드
now - 지금 탐색중인 노드
필요한 배열(vector)
adj - vector 형 배열로 인접리스트(트리)구현
visited - 방문체크
parents - i 번째 노드의 부모
깊이 우선 탐색(DFS)
1. 루트가 1이므로 처음 now 값 1로 전달
2. 1부터 자신의 자식 노드를 탐색
3. 다음에 탐색할 노드의 부모를 now로 설정하고 parents[다음 탐색할 노드] 에 now 값을 넣는다
코드
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
using namespace std; | |
vector<vector<int>> adj; | |
vector<bool> visited; | |
vector<int>parents; | |
void dfs(int now) | |
{ | |
visited[now] = true; | |
for(int i : adj[now]){ | |
if(!visited[i]){ | |
parents[i] = now; | |
dfs(i); | |
} | |
} | |
} | |
int main() | |
{ | |
ios_base :: sync_with_stdio(false); | |
cin.tie(NULL); | |
cout.tie(NULL); | |
int N; | |
cin >> N; | |
adj.resize(N + 1); | |
parents.resize(N + 1); | |
visited.resize(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); | |
} | |
dfs(1); | |
for (int i = 2; i <= N; i++) | |
cout << parents[i] << "\n"; | |
} |
'algorithm > 백준' 카테고리의 다른 글
[C++] 백준 2747번 : 피보나치 수 (0) | 2021.03.13 |
---|---|
[C++] 백준 1991번 : 트리 순회 (0) | 2021.03.01 |
[python] 백준 11653번 : 소인수분해 (0) | 2021.02.24 |
[text] 백준 11506 : 占쏙옙 (0) | 2021.02.22 |
[python] 백준 10872 : 팩토리얼 (0) | 2021.02.22 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
TAG
- 7567
- 1
- 4
- web
- programmers
- 나머지
- 21758
- 괄호
- 카카오 2021 블라인드 테스트
- 꿀따기
- forensic
- HackCTF
- 피보나치
- 스택
- 👼
- boj
- 프로그레머스
- 직업군 추천
- 파이썬
- openCV
- 다익스트라
- 백준
- 넓이
- 더하기
- c++
- FIBO
- math
- python
- 쇠막대기
- 2
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함