www.acmicpc.net/problem/1068

 

1068번: 트리

첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다

www.acmicpc.net

각 노드의 부모노드가 입력으로 주어집니다. (루트노드인 경우에는 -1이 주어집니다.)

그리고 삭제할 노드가 주어집니다.

노드를 삭제하면 해당 노드의 자식노드들까지 모두 삭제됩니다.

노드를 삭제한 후의 리프노드 갯수를 구하는 문제입니다.

 

입력이 들어오면 ArrayList로 그래프를 만들어줍니다.

그리고 입력으로 -1이 주어지면 루트노드이므로 저장해둡니다.

 

이제 root를 시작으로 dfs를 돌려줍니다.

만약 v가 삭제할 노드면 바로 리턴시켜주고,

v의 자식이 없으면 (list[v].size() == 0) 리프노드입니다. => ans++

v의 자식이 1개이고 그게 삭제할 노드면 v는 리프노드가 됩니다. => ans++

위의 예외처리만 해주고 dfs를 돌립니다.

 

 

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<Integer> list[];
    static int N, deleteNode, root, ans;
 
    static void dfs(int v) {
        if (v == deleteNode)
            return;
 
        if (list[v].size() == 0) {
            ans++;
            return;
        }
 
        for (int i = 0; i < list[v].size(); i++) {
            int next = list[v].get(i);
            
            if(list[v].size()==1 && next == deleteNode) {
                ans++;
                return;
            }
            
            dfs(next);
        }
    }
 
    static void input() throws Exception {
        int x;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        list = new ArrayList[N];
        for (int i = 0; i < N; i++)
            list[i] = new ArrayList<>();
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            x = Integer.parseInt(st.nextToken());
            if (x != -1)
                list[x].add(i);
            else
                root = i;
        }
 
        st = new StringTokenizer(br.readLine());
        deleteNode = Integer.parseInt(st.nextToken());
    }
 
    public static void main(String[] args) throws Exception {
        input();
        dfs(root);
        System.out.println(ans);
    }
}
 cs

'algorithm > dfs' 카테고리의 다른 글

boj 16927 배열 돌리기 2  (0) 2021.02.10
boj 16926 배열 돌리기 1  (0) 2021.02.10
boj 9202 Boggle  (0) 2021.02.02
boj 15666 N과 M (12)  (0) 2021.01.31
boj 15665 N과 M (11)  (0) 2021.01.30

www.acmicpc.net/problem/13116

 

13116번: 30번

첫 번째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 50 000)가 주어진다. 이후 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 구성되어 있으며, 각 줄에는 두 개의 정수 A와 B (1 ≤ A, B ≤ 1

www.acmicpc.net

사실 링크없이 이문제만 올려놔도 될 정도입니다..

위의 사진처럼 1 ~ 1023까지 perfect binary tree를 구성하고 있습니다.

여기서 a와 b의 최소 공통조상노드를 구하는 문제입니다.

 

트리는 고정이기때문에 depth와 parent는 입력을 받기전에 미리 구성해줍니다.

우선 dfs로 탐색을 진행하여 노드의 깊이를 저장해줍니다.

dfs로 탐색을 진행하면서 parent[v][0]에 부모노드인 v / 2를 저장합니다.

그 다음 parent배열에 자신의 1, 2, 4, 8, ... (2^N)번째 조상노드를 저장합니다.

 

입력으로 x, y를 받으면 x와 y의 최소 공통조상노드를 구합니다.

우선 y의 깊이가 더 크게 맞춰놓고

y의 깊이를 x에 맞춰줍니다.

 

그 다음 x와 y의 조상이 같아질때까지

x = parent[x][i]

y = parent[y][i]

연산을 반복합니다.

 

최종적으로 parent[x][0]을 출력해줍니다.

 

 

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int depth[] = new int[1024];
    static int parent[][] = new int[1024][11];
 
    static void dfs(int v, int d) {
        depth[v] = d;
        parent[v][0] = v / 2;
 
        int next = v * 2;
 
        if (next >= 1024)
            return;
 
        dfs(next, d + 1);
        dfs(next + 1, d + 1);
    }
 
    static void init() {
        dfs(1, 1);
        for (int j = 1; j < 11; j++) {
            for (int i = 1; i <= 1023; i++) {
                parent[i][j] = parent[parent[i][j - 1]][j - 1];
            }
        }
    }
 
    static int lca(int x, int y) {
        if (depth[x] > depth[y]) {
            int tmp = x;
            x = y;
            y = tmp;
        }
 
        for (int i = 10; i >= 0; i--) {
            if (depth[y] - depth[x] >= (1 << i)) {
                y = parent[y][i];
            }
        }
 
        if (x == y)
            return x;
 
        for (int i = 10; i >= 0; i--) {
            if (parent[x][i] != parent[y][i]) {
                x = parent[x][i];
                y = parent[y][i];
            }
        }
        
        return parent[x][0];
    }
 
    static void input() throws Exception {
        int u, v;
        st = new StringTokenizer(br.readLine());
        u = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());
 
        sb.append(lca(u, v) * 10 + "\n");
    }
 
    public static void main(String[] args) throws Exception {
        init();
        st = new StringTokenizer(br.readLine());
        int tc = Integer.parseInt(st.nextToken());
        while (tc-- > 0) {
            input();
        }
        
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > LCA' 카테고리의 다른 글

boj 1626 두 번째로 작은 스패닝 트리  (0) 2021.04.02
boj 15481 그래프와 MST  (0) 2021.04.01
boj 15480 LCA와 쿼리  (0) 2021.02.14
boj 11438 LCA 2  (0) 2021.02.11
boj 11437 LCA  (0) 2021.02.11

www.acmicpc.net/problem/9372

 

9372번: 상근이의 여행

첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가

www.acmicpc.net

이문제는 모든 국가를 여행하는데 타야하는 비행기의 최소 갯수를 출력하는 문제입니다.

입력으로는 무조건 연결그래프만 주어지며, N개의 국가를 모두 연결하기 위해서는 최소 N - 1개의 간선만 있으면 됩니다.

입력만 다받고 N - 1를 출력해줍시다.

 

 

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
31
32
33
34
35
36
package BOJ.data_structure;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Boj9372 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int N;
 
    static void input() throws Exception {
        int M, x;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            x = Integer.parseInt(st.nextToken());
        }
 
        sb.append(N - 1 + "\n");
    }
 
    public static void main(String[] args) throws Exception {
        st = new StringTokenizer(br.readLine());
        int tc = Integer.parseInt(st.nextToken());
        while (tc-- > 0) {
            input();
        }
        
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 21939 문제 추천 시스템 Version 1  (0) 2022.02.11
boj 17299 오등큰수  (0) 2021.02.22
boj 1158 요세푸스 문제  (0) 2021.02.09
boj 1918 후위 표기식  (0) 2021.02.05
boj 1935 후위 표기식2  (0) 2021.02.05

www.acmicpc.net/problem/5639

 

5639번: 이진 검색 트리

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다

www.acmicpc.net

자바로 트리를 처음 구현해보았습니다..

 

입력이 전위순회이므로 들어오는 대로 트리에 넣어줍니다.

이진 검색 트리는 x가 들어오면 트리의 루트노드의 값부터 비교를 합니다.

노드의 값보다 작으면 왼쪽 서브트리이고,

노드의 값보다 크면 오른쪽 서브트리로 이동하면 되고

 

이동하려는 서브트리가 null이면 그곳에 newnode를 삽입하면 됩니다.

출력은 후위순회로 출력입니다.

 

 

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuffer sb = new StringBuffer();
 
    static class tree {
        int x;
        tree llink;
        tree rlink;
 
        tree() {
        }
 
        tree(int x, tree llink, tree rlink) {
            this.x = x;
            this.llink = llink;
            this.rlink = rlink;
        }
    }
 
    static tree node = new tree();
 
    static void addnode(int x) {
        tree newnode = new tree(x, null, null);
 
        if (node.x == 0) {
            node.x = x;
            return;
        }
 
        tree p = node;
 
        while (p != null) {
            if (p.x > x) {
                if (p.llink == null) {
                    p.llink = newnode;
                    break;
                } else
                    p = p.llink;
            } else {
                if (p.rlink == null) {
                    p.rlink = newnode;
                    break;
                } else
                    p = p.rlink;
            }
        }
    }
 
    static void postorder(tree t) {
        if (t.llink != null)
            postorder(t.llink);
        if (t.rlink != null)
            postorder(t.rlink);
        sb.append(t.x + "\n");
    }
 
    static void input() throws Exception {
        String st;
        while (true) {
            st = br.readLine();
            if (st == null || st.length() == 0)
                break;
 
            int x = Integer.parseInt(st);
            addnode(x);
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        postorder(node);
        System.out.println(sb.toString());
    }
}
 cs

'algorithm > data-structure' 카테고리의 다른 글

boj 17298 오큰수  (0) 2021.01.25
boj 4358 생태학  (0) 2021.01.25
boj 1991 트리 순회  (0) 2021.01.22
boj 11003 최솟값 찾기  (0) 2021.01.22
boj 2517 달리기  (0) 2021.01.22

www.acmicpc.net/problem/1991

 

1991번: 트리 순회

첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자

www.acmicpc.net

트리 순회의 간단한 문제입니다.

 

input으로 주어지는 노드는 A~Z까지 26개이므로 숫자로 변환하여 인덱스화 하였습니다.

list배열에 각 노드의 왼쪽자식을 [0]에, 오른쪽 자식을 [1]에 저장하여 순회하였습니다.

 

 

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package BOJ.data_structure;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Boj1991 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuffer sb = new StringBuffer();
    static int list[][] = new int[27][2];
    static int N;
 
    static void preorder(int v) {
        sb.append((char) (v + 'A'));
        if (list[v][0] != -1)
            preorder(list[v][0]);
        if (list[v][1] != -1)
            preorder(list[v][1]);
    }
 
    static void inorder(int v) {
        if (list[v][0] != -1)
            inorder(list[v][0]);
        sb.append((char) (v + 'A'));
        if (list[v][1] != -1)
            inorder(list[v][1]);
    }
 
    static void postorder(int v) {
        if (list[v][0] != -1)
            postorder(list[v][0]);
        if (list[v][1] != -1)
            postorder(list[v][1]);
        sb.append((char) (v + 'A'));
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            char x = st.nextToken().charAt(0);
            char l = st.nextToken().charAt(0);
            char r = st.nextToken().charAt(0);
 
            if (l == '.')
                list[x - 'A'][0] = -1;
            else
                list[x - 'A'][0] = l - 'A';
 
            if (r == '.')
                list[x - 'A'][1] = -1;
            else
                list[x - 'A'][1] = r - 'A';
 
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        preorder(0);
        sb.append("\n");
        inorder(0);
        sb.append("\n");
        postorder(0);
        sb.append("\n");
        System.out.println(sb.toString());
    }
}
cs

'algorithm > data-structure' 카테고리의 다른 글

boj 4358 생태학  (0) 2021.01.25
boj 5639 이진 검색 트리  (0) 2021.01.24
boj 11003 최솟값 찾기  (0) 2021.01.22
boj 2517 달리기  (0) 2021.01.22
boj 3425 고스택  (0) 2021.01.22

+ Recent posts

티스토리툴바