알고리즘 스터디 - dfs

11725

• 알고리즘 : dfs
• 난이도 : 실버2

접근

• bfs로 접근 했던 방식을 dfs로 접근하였다.
• 노드를 클래스로 분리하려고 했는데 자료구조를 따로 빼는게 훨씬 수월했다.

코드

package org.example;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
	static List<List<Integer>> graph = new ArrayList<>();
	static int[] parents;
	static boolean[] visited;
	static int N;
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(reader.readLine());
		parents = new int[N + 1];
		visited = new boolean[N + 1];

		for(int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());
		}
		for(int i = 0; i < N - 1; i++) {
			String[] line = reader.readLine().split(" ");
			int a = Integer.parseInt(line[0]);
			int b = Integer.parseInt(line[1]);
			graph.get(a).add(b);
			graph.get(b).add(a);
		}
		dfs(1);
		for(int i = 2; i <= N; i++){
			System.out.println(parents[i]);
		}
	}
	static void dfs(int node) {
		visited[node] = true;
		for(int i : graph.get(node)){
			if(!visited[i]) {
				parents[i] = node;
				dfs(i);
			}
		}
	}

}