본문 바로가기

DFS12

20220210 트리, BFS, DFS 트리 트리의 개념 비선형 구조 원소들간에 1:n 관례를 가지는 자료구조 트리의 정의 노드 - 트리의 원소 한개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족 노드 중 최 상위 노드를 루트(root)라고 한다. 나머지 노드들은 n(≥0)개의 분리 집합으로 분리될 수 있다. 분리된 집합들을 각각 하나의 트리가 되며, 루트의 부 트리(subtree)라고 한다. 간선 - 노드와 노드를 연결하는 선으로 부모 노드와 자식 노드를 연결 형제 노드(sibling node) - 같은 부모 노드의 자식 노드들 조상 노드(ancestor node) - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 서브 트리(subtree) - 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리 자손 노드(deceden.. 2022. 2. 10.
Baekjoon 1260 DFS와 BFS JAVA 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개.. 2022. 2. 5.
Baekjoon 15649 N과 M (1) JAVA 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 코드 import .. 2022. 1. 17.
728x90
728x90

티스토리툴바