목록트리 (13)

1일1알

백준 14675번 단절점과 단절선 C++

https://www.acmicpc.net/problem/14675 14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net 트리에서는 단절점과 단절선의 조건이 아래와 같다. 단절점 : 리프 노드가 아니면 전부 단절점이다. 단절선 : 모든 선이 단절선이다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include..
알고리즘 2023. 5. 26. 12:40
백준 24230번 트리 색칠하기 C++

https://www.acmicpc.net/problem/24230 24230번: 트리 색칠하기 정점이 $N$개인 트리가 있다. 정점에는 1부터 $N$까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해 www.acmicpc.net 부모와 자식의 색이 다르다면 그부분에서 색을 칠해야 하므로 cnt 1 증가 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64..
알고리즘 2023. 2. 18. 11:58
백준 1240번 노드사이의 거리 C++

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net dfs #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n, m; int ans; vector graph; vector visited; void d..
알고리즘 2023. 1. 29. 12:05
백준 16437번 양 구출 작전 C++

https://www.acmicpc.net/problem/16437 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net 각 섬에서 1번 섬으로 갈 수 있는 유일한 경로가 하나는 꼭 있고 연결되어있는 섬은 각 섬당 하나씩 주어지기 때문에 1번 섬이 루트 노드인 트리로 나타낼 수 있다. 각 섬들을 돌면서 1번 섬으로 갈 수 있는 양의 수를 구하면 되는데, 그냥 구하면 시간초과가 난다. 내가 사용한 시간초과를 해결하기 위한 방법은 두가지이다. 1. 1번 섬으로 가는 도중 만나는 양을 데리고 간다. 2...
알고리즘 2023. 1. 6. 14:44
백준 25516번 거리가 k이하인 트리 노드에서 사과 수확하기 C++

https://www.acmicpc.net/problem/25516 25516번: 거리가 k이하인 트리 노드에서 사과 수확하기 n개의 정점과 n - 1개의 간선으로 구성된 트리 T가 있다. 정점 번호는 0부터 n - 1까지이고 0번 정점이 루트이다. 모든 간선의 길이는 1이다. 트리 T의 각 정점에는 사과가 0개 또는 1개 놓여있다. 루 www.acmicpc.net dfs #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long..
알고리즘 2022. 11. 18. 13:53
백준 2263번 트리의 순회 C++

포스트오더는 루트를 마지막에 순회하는것을 이용해서 인오더에서 루트값을 찾아서 작은 트리로 분할해가면서 루트를 출력하는 방식으로 풀었다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n; vector inOrderIndex; vector postOrder; void PrintRoot(int inOrderStart, int inOrderEnd, int postOrderStart, int postOrderEnd)..
알고리즘 2022. 6. 22. 12:08
이전 Prev 1 2 3 Next 다음