[백준] 24482. 깊이 우선 탐색 4 (Java)

 

문제

24482번: 알고리즘 수업 - 깊이 우선 탐색 4

 

 

알고리즘

그래프, 깊이우선탐색(DFS)

 

 

풀이

초기화

1. 양방향 인접리스트로 그래프를 저장

2. 모든 정점의 깊이를 -1로 초기화

3. 정점 번호를 내림차순으로 방문한다는 조건이 있으므로 인접 리스트를 내림차순으로 정렬한다.

 

DFS

R을 시작으로

현재 정점의 깊이를 저장하고 깊이를 1씩 늘리며

방문하지 않은(depth[next] != -1) 다음 정점에 대해 재귀 호출한다.

 

 

코드

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.List;
import java.util.StringTokenizer;

public class Main {
	static int[] depth;
	static List<Integer>[] graph;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int R = Integer.parseInt(st.nextToken());

		depth = new int[N + 1];
		Arrays.fill(depth, -1);
		
		graph = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++)
			graph[i] = new ArrayList<>();

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());

			graph[u].add(v);
			graph[v].add(u);
		}

		for (int i = 1; i <= N; i++)
			Collections.sort(graph[i], Collections.reverseOrder());

		dfs(R, 0);

		StringBuilder sb = new StringBuilder();
		for(int i=1; i<=N; i++)
			sb.append(depth[i]).append(" ");
		System.out.println(sb);
	}
	private static void dfs(int cur, int d) {
		depth[cur] = d;
		
		for(int next: graph[cur]) {
			if(depth[next] != -1) continue;
			dfs(next, d + 1);
		}
	}
}