[백준] 24481 알고리즘 수업 - 깊이 우선 탐색 3 - DFS(깊이우선탐색) JAVA

https://www.acmicpc.net/problem/24481

코드설명

DFS(깊이우선탐색) 을 활용합니다.

 

문제에서는 깊이를 갱신합니다. DFS에서는 한번 실행되면 해당 시작함수로 돌아올떄까지 계속해서 깊이가 증가(depth + 1)하므로 depth + 1 을 매개변수에 넣어주면서 탐색하면 됩니다.

코드

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, A, B, X, R;
//	static int answer = 0;
	static int[] answer;
	static ArrayList<Integer>[] arr = new ArrayList[100001];
	static boolean[] visited = new boolean[100001];
	static int rank = 1;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		
		answer = new int[N];
		Arrays.fill(answer,-1);
		for(int i=0;i<100001; i++) {
			arr[i] = new ArrayList<Integer>();
		}
		
		for(int i=0;i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1;
			int v = Integer.parseInt(st.nextToken()) - 1;
			arr[u].add(v);
			arr[v].add(u);
		}
		
		for(int i=0;i<N;i++) {
			Collections.sort(arr[i]);
		}
		
		DFS(0, R-1);
		
		for(int i=0;i<N;i++) {
			System.out.println(answer[i]);
		}
	}
	
	static void DFS(int depth, int now) {
		visited[now] = true;
		answer[now] = depth; 
		for(int next =0; next < arr[now].size(); next++) {
			int nextNode = arr[now].get(next);
			if(visited[nextNode] == true) continue;
			DFS(depth + 1, nextNode);
		}
	}
}