[백준] 24479 알고리즘 수업 - 깊이 우선 탐색 1 - DFS(깊이우선탐색) JAVA

https://www.acmicpc.net/problem/24479

코드설명

DFS(깊이우선탐색)을 활용합니다.

 

문제에서 주어진 의사코드대로 구현하면 되고, 

행렬로 그래프를 표현할시 메모리 초과가 발생하므로, LinkedList 형식으로 구현합니다.

코드

package Main;

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 Main {
	static int N, M, S, P, K, A, B, X, R;
//	static int answer = 0;
	static int[] answer;
	static ArrayList<Integer>[] arr = new ArrayList[100001];
	static boolean[] visited = new boolean[100001];
	static int rank = 1;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		
		answer = new int[N];
		for(int i=0;i<100001; i++) {
			arr[i] = new ArrayList<Integer>();
		}
		
		for(int i=0;i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1;
			int v = Integer.parseInt(st.nextToken()) - 1;
			arr[u].add(v);
			arr[v].add(u);
		}
		
		for(int i=0;i<N;i++) {
			Collections.sort(arr[i]);
		}
		
		DFS(R-1);
		
		for(int i=0;i<N;i++) {
			System.out.println(answer[i]);
		}
	}
	
	static void DFS(int now) {
		visited[now] = true;
		answer[now] = rank++; 
		for(int next =0; next < arr[now].size(); next++) {
			int nextNode = arr[now].get(next);
			if(visited[nextNode] == true) continue;
			DFS(nextNode);
		}
	}
}