11725_트리의 부모 찾기

사용 알고리즘: dfs, bfs

사용 언어: java

 

bfs썼을 때 시간

 

dfs썼을 때 시간

 

 

bfs코드

import java.util.*;

public class Main_bj_11725_bfs {
    static int n;
    static boolean[] visit;
    static int[] parent;
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        parent = new int[n+1];
        visit = new boolean[n+1];
        graph = new ArrayList<>(n+1);
        for (int i = 0; i < n+1; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for (int i = 1; i < n; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();

            graph.get(s).add(e);
            graph.get(e).add(s);
        } //입력

        visit[1] = true;
        bfs(1);

        for(int i=2; i<n+1; i++){
            System.out.println(parent[i]);
        }
    }

    private static void bfs(int root) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(root);

        while (!q.isEmpty()) {
            int cur = q.poll();
            visit[cur] = true;

            for (int i = 0; i < graph.get(cur).size(); i++) {
                int nxt = graph.get(cur).get(i);
                if( !visit[nxt] ){

                    parent[nxt] = cur;
                    q.offer(nxt);
                }
            }
        }
    }
}

 

 

dfs

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	static int N;
	static ArrayList<Integer>[] tree ;
	static int[] whoIsYourParent, visited;
	

	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		
		N =sc.nextInt();
		whoIsYourParent = new int[N+1]; //인덱스 0 버리기
		visited = new int[N+1]; //방문하면 -1로 바꾸기
		tree = new ArrayList[N+1];
		
		for(int i=1; i<=N; i++) tree[i] = new ArrayList<>();
		for(int i=0; i<N-1; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			tree[a].add(b);
			tree[b].add(a);
		} //입력 받
		
		//tree 입력 받은 거 확인
//		for(int i=1; i<N+1; i++) {
//			System.out.println(tree[i]);
//		}
		visited[index] = -1;
		dfs(1);
		
		//드디어 부모 출력
		for(int i=2; i<=N; i++) {
			System.out.println(whoIsYourParent[i]);
		}
		
	} // main 끝


	private static void dfs(int index) {
		
		for(int i: tree[index]) {
			if ( visited[i]==0 ) {
				visited[i] = -1;
				whoIsYourParent[i] = index;
				dfs(i);
			}
		}
	}

}

 

이슈:

시간이 매우 오래 걸림 (java 언어 특성 상 어쩔 수 없는 거 같은)

 

해결:

위의 코드에서 사용하지는 않았지만, BufferedReader, StringBuilder 등을 대신 사용하기