본문 바로가기

Algorithm/BOJ211

[BOJ]11725번 : 트리의 부모 찾기 (c++) https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 방법 1: dfs #include #include using namespace std; int root = 1; void dfs(vector& tree, vector& parent, int now) { // 현재 노드의 자식 노드 탐색 for (int child : tree[now]) { // 아직 방문하지 않은 parent[자식노드]에 현재노드 저장 후 dfs 재귀함수 호출 if (parent[child] == 0) { parent[child] = now; .. 2020. 5. 31.
[BOJ] 2250번: 트리의 높이와 너비 (c++) https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. ��www.acmicpc.net 중위 순회로 레벨별 최소 인덱스, 최대 인덱스 구하기 --> 최대 차이 구하기#include #include #include #include using namespace std;struct node { int parent, left, right;};struct level { int min, max;};int order = 1;int max_depth;// parent가 0 인 .. 2020. 5. 31.
[BOJ]1991번: 트리 순회 (c++) https://www.acmicpc.net/problem/1991 1991번: 트리 순회첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자www.acmicpc.net #include #include #include using namespace std;struct node { int left, right;};// 전위 순회 출력void dfs_preorder(vector &tree, int n){ if (n == -1) { return; } cout (n + 'A'); dfs_preorder(tree, tree[n].left); dfs_preorder(tre.. 2020. 5. 31.
[BOJ]1261번: 알고스팟 (c++) https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net #include #include #include using namespace std; int bfs(vector &map) { // x, y: 위치, cnt : 벽을 부순 횟수 struct info { int x, y, cnt; }; int dir_x[] = { 0, 1, 0, -1 }; int dir_y[] = { 1, 0, -1, 0 }; int N = map.size().. 2020. 5. 30.

티스토리툴바