[java] 트리와 DFS

백준 11725: 트리의 부모 찾기

11725번: 트리의 부모 찾기

문제를 해결하기 위해서 사용할 것

✅트리 데이터를 저장할 인접 리스트 visited
✅ 방문 기록 저장 배열 tree
✅ 부모 노드 저장 정답 배열 parent

import java.io.*;
import java.util.*;

//무엇이 필요한가
//트리 데이터를 저장할 인접 리스트
//방문 기록 저장 배열
//부모 노드 저장 정답 배열

public class tmp {
	static int n;
	static boolean[] visited;
	static ArrayList<Integer> tree[];
	static int parent[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        visited = new boolean[n+1];
        tree = new ArrayList[n+1];
        parent = new int[n+1];
        
      //tree 인접 리스트에 n-1개의 트리 데이터 저장 
        for(int i = 0; i < tree.length; i++) {
        	tree[i] = new ArrayList<>();
        } 
        
        //데이터 추가해주자
        for(int i = 1; i < n; i++) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	int num1 = Integer.parseInt(st.nextToken());
        	int num2 = Integer.parseInt(st.nextToken());
        	tree[num1].add(num2);
        	tree[num2].add(num1);
        }
        DFS(1); //1부터 DFS 탐색을 시작하자
        for(int i = 2; i <= n; i++) {
        	System.out.println(parent[i]);
        }
        
    }
    static void DFS(int node) {
    	visited[node] = true; //방문한 노드는 true로 바꾸어 주자
    	for(int n: tree[node]) { //현재 위치한 노드와 인접한 노드를 탐색한다
    		if(!visited[n]) { //방문하지 않은 노드가 있으면
    			parent[n] = node; //부모 노드를 저장 
    			DFS(n);
    		}
    	}
    }
}

 

백준 1068: 트리: 리프 노드 찾기

1068번: 트리

리프 노드란: 자식 개수가 0인 노드

트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성

 

리프 노드를 삭제하는 방법 = 탐색 알고리즘 수행할 때나 제거하는 노드가 나왔을 때 탐색을 종료

import java.io.*;
import java.util.*;

public class Main{
	static int n;
	static int root;
	static int delete;
	static int count;
	static boolean[] visited;
	static ArrayList<Integer> tree[];
	static int parent[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        visited = new boolean[n+1];
        tree = new ArrayList[n+1];

        for(int i = 0; i < tree.length; i++) {
        	tree[i] = new ArrayList<>();
        } 
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
        	int num = Integer.parseInt(st.nextToken());
        	if(num != -1) {
        		tree[i].add(num);
        		tree[num].add(i);
        	}
        	else
        		root = i;
        }
        delete = Integer.parseInt(br.readLine());
        if(delete == root)
        	System.out.println(0);
        else {
        	DFS(root);
        	System.out.println(count);
        }
        
    }
    static void DFS(int node) {
    	visited[node] = true; //방문한 노드는 true로 바꾸어 주자
    	int child = 0; // 리프 노드는 자식 개수가 0이므로 자식 노드 개수 저장하는 child 변수
    	for(int n: tree[node]) { //현재 위치한 노드와 인접한 노드를 탐색한다
    		 //방문하지 않고 삭제할 노드가 아니라면.
    		//즉 아예 탐색을 해버리지 않는 것으로 '삭제'라는 작업을 구현
    		if(!visited[n] && n != delete) {
    			child++; //탐색할 자식이 있으니 +1
    			DFS(n);
    		}
    	}
    	if(child == 0)
    		count++; //자식 노드가 0이면 리프노드로 
    }
}