BEAKJOON / 백준 - JAVA 24482번 알고리즘 수업 - 깊이 우선 탐색 4

2024.08.29기준 - 실버2

728x90

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 정점의 개수, 간선의 개수, 시작 정점이 주어질 때, dfs를 이용하여 1 ~ n까지의 정점의 깊이를 출력하는 문제입니다.

 

주의점은 문제에서 시간 초과가 계속 나왔는데... LinkedList<>()로 접근을 해서 시간복잡도가 더 늘어난걸 알게되었습니다!..

정렬을 이용할 때는 LinkedList보다는 ArrayList를 사용해야 된다는 정보를 얻을 수 있는 문제였습니다.

 

1. 정점의 수는 1부터 시작하기 때문에 depth를 n + 1크기로 생성해 간선과 깊이를 초기화 시켜주었습니다.

depth = new int[n + 1];
list = new ArrayList<>();
for (int i = 0; i <= n; i++) {
    list.add(new ArrayList<>());
    depth[i] = -1;
}

 

2. 입력 받은 간선은 양방향이기 때문에 start -> end, end -> start로 2개의 데이터를 저장해줍니다.

int start, end;
while (m-- > 0) {
    st = new StringTokenizer(br.readLine());
    start = Integer.parseInt(st.nextToken());
    end = Integer.parseInt(st.nextToken());

    list.get(start).add(end);
    list.get(end).add(start);
}

 

3. 저장된 간선들을 내림차순으로 정렬 해줍니다.

// 내림차순 정렬
list.forEach((x -> Collections.sort(x, Collections.reverseOrder())));

 

4. dfs 함수를 호출하여 깊이를 저장해줍니다.

시작 정점을 기준으로 깊이는 0으로 시작해 재귀 함수를 통해 깊이가 저장되지 않은 정점이면 깊이를 계속 올려주며 저장해줍니다.

private static void dfs(int index, int count) {
depth[index] = count;

for (int i : list.get(index)) {
    if (depth[i] == -1) {
        dfs(i, count + 1);
    }
}
}

 

5. 저장된 깊이 배열을 1부터 출력해줍니다.

dfs(r, 0);
for (int i = 1; i <= n; i++) {
    sb.append(depth[i]).append("\n");
}

 

 

 

코드

package Main;

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

public class Main {
	
	static int[] depth;
	static ArrayList<ArrayList<Integer>> list;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		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];
		list = new ArrayList<>();
		for (int i = 0; i <= n; i++) {
			list.add(new ArrayList<>());
			depth[i] = -1;
		}
		
		int start, end;
		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			start = Integer.parseInt(st.nextToken());
			end = Integer.parseInt(st.nextToken());
			
			list.get(start).add(end);
			list.get(end).add(start);
		}
		
		// 내림차순 정렬
		list.forEach((x -> Collections.sort(x, Collections.reverseOrder())));
		
		dfs(r, 0);
		for (int i = 1; i <= n; i++) {
			sb.append(depth[i]).append("\n");
		}
		
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
	
	private static void dfs(int index, int count) {
		depth[index] = count;
		
		for (int i : list.get(index)) {
			if (depth[i] == -1) {
				dfs(i, count + 1);
			}
		}
	}
}