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

Silver II

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

---

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

 

문제 풀이

 

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 _24483_ { //알고리즘 수업 - 깊이 우선 탐색 5
	static ArrayList<ArrayList<Integer>> arr;
	static int d[], t[];
	static int idx;

	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 int[n];
		t=new int[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));
		}

		d[r]=0;
		t[r]=1;
		idx=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)]=idx++;
				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이다.

 

---

마무리🤔

 

---