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

Silver II

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

---

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

 

문제 풀이

 

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

 

 

 

 my solution (Java)

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

public class _24481_ { // 알고리즘 수업 - 깊이 우선 탐색 3
	static ArrayList<ArrayList<Integer>> arr;
	static int d[];
	
	public static void main(String[] args) throws IOException {
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		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];
		
		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;
		dfs(r);
		
		for(int i=0; i<n; i++) {
			bw.write(d[i]+"\n");
		}
		bw.flush();
	}

	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;
				dfs(arr.get(r).get(i));
			}
		}
	}
}

 

Main

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

- arr : 인접 리스트

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

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

- 시작 정점의 노드의 깊이는 0으로 초기화 후 dfs 함수 호출

- d 배열 출력

 

dfs(시작 정점 r)

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

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

 

---

마무리🤔

 

---