본문 바로가기

dfs

[BOJ] 백준 22856번 트리 순회 (Java)
Dot Algo∙ DS/PS 2022. 3. 18. [BOJ] 백준 22856번 트리 순회 (Java) #22856 트리 순회 난이도 : 골드 4 유형 : 트리 순회 / DFS 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net ▸ 문제 노드가 N개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. 이때 루트 노드는 항상 1번 노드이다. 유사 중위 순회는 루트 노드에서 시작하며, 다음과 같이 진행된다. 현재 위치한 노드의 왼쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 왼쪽 자식 노드로..
[BOJ] 백준 1595번 북쪽나라의 도로 (Java)
Dot Algo∙ DS/PS 2022. 3. 14. [BOJ] 백준 1595번 북쪽나라의 도로 (Java) #1595 북쪽나라의 도로 난이도 : 골드 3 유형 : 트리의 지름 / dfs 1595번: 북쪽나라의 도로 입력은 여러줄에 걸쳐 주어진다. 입력의 각 줄은 세 개의 양의 정수로 구성되어있는데, 각각은 차례대로 서로 다른 두 도시의 번호와 두 도시를 연결하는 도로의 길이를 의미한다. 모든 도로는 www.acmicpc.net ▸ 문제 두 도시 사이에 도로를 만드는 일은 매우 비싸다. 때문에 북쪽나라는 특정 도시를 두 번 이상 지나가지 않고서 임의의 두 도시간을 이동하는 경로가 유일하도록 도로가 설계되어 있다. 또한 북쪽나라의 모든 도시는 다른 모든 도시로 이동할 수 있다고 한다. 이때, 거리가 가장 먼 두 도시 사이의 거리를 출력하는 것이 당신의 임무이다. 북쪽나라에는 최대 10,000개의 도시가 있을 수 ..
[알고리즘] 단절선 (백준 11400번 풀이)
Dot Algo∙ DS/PS 2022. 3. 2. [알고리즘] 단절선 (백준 11400번 풀이) #11400 단절선 난이도 : 플레 5 유형 : 그래프 / 단절선 / DFS 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net ▸ 문제 그래프가 주어졌을 때, 단절선을 모두 구해 출력하는 프로그램을 작성하시오. 단절선이란 그 간선을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 간선을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 간선을 말한다. ▸ 입력 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000..
[BOJ] 백준 20530번 양분 (Java)
Dot Algo∙ DS/PS 2022. 2. 26. [BOJ] 백준 20530번 양분 (Java) #20530 양분 난이도 : 골드 2 유형 : 트리 / DFS 20530번: 양분 첫째 줄에 두 자연수 $N$, $Q$가 주어진다. 주어지는 그래프의 정점과 간선의 개수가 $N$개이며 쿼리가 $Q$개 주어진다는 것을 의미한다. 둘째 줄부터 $N$개의 줄에는 $i$번 간선이 연결하는 두 정점 www.acmicpc.net ▸ 문제 나무 T는 양분을 먹고 자란다. 원래 나무는 정점 N개와 간선 N−1개로 구성되어야 하지만, 양분을 너무 많이 먹어버린 나머지 나무 T는 N개의 간선을 갖게 되었다. 더 이상 트리가 아니기 때문에 T는 꿈의 무대인 트리와 쿼리에 등장하지 못한다. 슬퍼하고 있는 T 위해 정휘는 새로운 문제를 만들어 주었다. N개의 정점과 N개의 간선으로 이루어진 연결 그래프 T가 주어진다. 정점은 ..
[BOJ] 백준 2023번 신기한 소수 (Java)
Dot Algo∙ DS/PS 2022. 2. 9. [BOJ] 백준 2023번 신기한 소수 (Java) #2023 신기한 소수 난이도 : 골드 5 유형 : 소수 / DFS /백트래킹 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net ▸ 문제 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다. 수빈이는 N자리의 숫자..
[BOJ] 백준 13325번 이진 트리 (Java)
Dot Algo∙ DS/PS 2022. 1. 21. [BOJ] 백준 13325번 이진 트리 (Java) #13325 이진 트리 난이도 : 골드 4 유형 : 트리 / DFS 13325번: 이진 트리 입력 데이터는 표준입력을 사용한다. 입력의 첫째 줄에는 포화이진트리의 높이를 나타내는 양의 정수 k(1 ≤ k ≤ 20)가 주어진다. 두 번째 줄에는 모든 에지들의 가중치가 주어진다. 에지들의 가 www.acmicpc.net ▸ 문제 각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다. 높이 k인 포화이진트리는 2k개의 리프를 포함하여 (2k+1 − 1)개의 노드를 가진다. 루트에서 어떤 리프까지의 거리는 루트에서 그 리프까지의 경로상에 있는 모든 에지들의 가중치를 더한 값이다. 이 문제에서는, 어떤 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 같도록 하고, 또한 에지 가중치..
[BOJ] 백준 14570번 나무 위의 구슬 (Java)
Dot Algo∙ DS/PS 2021. 12. 25. [BOJ] 백준 14570번 나무 위의 구슬 (Java) #14570 나무 위의 구슬 난이도 : 골드 2 유형 : 트리 / DFS 14570번: 나무 위의 구슬 이진 트리란, 위처럼 모든 노드의 자식의 수가 2개 이하인 트리이다. 각 노드에 쓰여 있는 수는 노드의 번호를 의미한다. 특히, 이 문제에서는 루트가 고정되어 있으며, 노드의 순서가 중요한(어 www.acmicpc.net ▸ 문제 이진 트리란, 위처럼 모든 노드의 자식의 수가 2개 이하인 트리이다. 각 노드에 쓰여 있는 수는 노드의 번호를 의미한다. 특히, 이 문제에서는 루트가 고정되어 있으며, 노드의 순서가 중요한(어떤 서브트리에서도 좌우를 변경할 수 없는) 이진 트리에 대해 다루기로 한다. 이진 트리의 루트에 구슬을 하나 올려놓으면 구슬은 아래와 같은 과정을 거쳐 떨어진다. 현재 구슬이 놓인 노드의..
[BOJ] 백준 7812번 중앙 트리 (Java)
Dot Algo∙ DS/PS 2021. 12. 24. [BOJ] 백준 7812번 중앙 트리 (Java) #7812 중앙 트리 난이도 : 플레 5 유형 : 트리 / DFS 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net ▸ 문제 트리는 사이클을 갖지 않는 연결된 그래프이다. 중앙 정점은 모든 정점으로 이르는 비용의 합이 가장 작은 정점이다. 트리의 정점 개수가 작은 경우에는 모든 경우의 수를 다 계산해보는 프로그램을 이용해 쉽게 구할 수 있다. 위의 그림은 가중치가 있는 트리로, 정점의 개수는 5개이다. 이 트리의 중앙 정점은 B이다. B-A = 2, B-D = 7, B-C = 1, B-E ..

티스토리툴바

티스토리툴바