[Baekjoon] 24484_알고리즘 수업 - 깊이 우선 탐색 6

Silver II

문제(출처: https://www.acmicpc.net/problem/24484)

---

< 알고리즘 수업 - 깊이 우선 탐색 6 >

 

문제 풀이

 

dfs로 탐색하면서 노드의 깊이와 노드의 방문 순서를 저장해 준다.

 

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class _24484_ { // 알고리즘 수업 - 깊이 우선 탐색 6 
	static ArrayList<ArrayList<Integer>> arr;
	static long d[], t[];
	static int index;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int r = Integer.parseInt(st.nextToken()) - 1;

		arr = new ArrayList<>();
		d = new long[n];
		t = new long[n];
		for (int i = 0; i < n; i++) {
			arr.add(new ArrayList<>());
			d[i] = -1;
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1;
			int v = Integer.parseInt(st.nextToken()) - 1;
			arr.get(u).add(v);
			arr.get(v).add(u);
		}

		for (int i = 0; i < n; i++) {
			Collections.sort(arr.get(i), Collections.reverseOrder());
		}

		d[r] = 0;
		t[r] = 1;
		index = 2;
		dfs(r);

		long result = 0;
		for (int i = 0; i < n; i++) {
			result += d[i] * t[i];
		}
		System.out.println(result);
	}

	private static void dfs(int r) {
		for (int i = 0; i < arr.get(r).size(); i++) {
			if (d[arr.get(r).get(i)] == -1) {
				d[arr.get(r).get(i)] = d[r] + 1;
				t[arr.get(r).get(i)] = index++;
				dfs(arr.get(r).get(i));
			}
		}
	}
}

 

Main

- 정점의 수 (n), 간선의 수 (m), 시작 정점 (r) 입력

- arr : 인접 리스트

   d : 노드의 깊이 (방문 여부를 확인하기 위해 -1로 초기화)

   t : 노드의 방문 순서

- 양방향으로 그래프 저장 및 내림차순으로 정렬

- 시작 정점의 노드의 깊이는 0, 노드의 방문 순서는 1로 초기화 후 dfs 함수 호출

-  result: d x t 합

 

dfs(시작 정점 r)

- 시작 정점의 인접 정점의 수만큼 반복하여 아직 방문하지 않은 노드인지 확인 (노드의 깊이가 -1이면 아직 방문 x) -> 노드의 깊이와 노드의 방문 순서 저장 후 dfs 호출

* 노드의 깊이는 전 노드의 깊이 +1이다.

 

---

마무리🤔

 

---