백준 - 1260 ( dfs & bfs)

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

public class Main{
	static boolean[] visited;
	static List<Integer>[] graph;
	
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	int N = Integer.parseInt(st.nextToken()); // 숫자 : 1 ~ N
    	int M = Integer.parseInt(st.nextToken()); // 간선 : M개
    	int V = Integer.parseInt(st.nextToken()); // 시작
    	
    	graph = new ArrayList[N+1];
    	for(int n = 1; n <= N; n++) {
    		graph[n] = new ArrayList<>();
    	}
    	
    	for(int n = 0; n < M; n++) {
    		st = new StringTokenizer(br.readLine());
    		int start = Integer.parseInt(st.nextToken());
    		int end = Integer.parseInt(st.nextToken());
    		graph[start].add(end);
    		graph[end].add(start);
    	}

    	for(int i = 1; i <= N; i++) {
    		Collections.sort(graph[i]);
    	}
    	visited = new boolean[N+1];
    	//DFS
    	dfs(V);
    	
    	System.out.println();
    	
    	visited = new boolean[N+1];
    	//BFS
    	bfs(V);
	}
	static void dfs(int V) {
		visited[V] = true;
		System.out.print(V + " ");
		
		for(int next : graph[V]) {
			if(!visited[next]) {
				dfs(next);
			}
		}
	}
	static void bfs(int V) {
		Queue<Integer> queue = new ArrayDeque<>();
		visited[V] = true;
		queue.offer(V);
		
		while(!queue.isEmpty()) {
			int v = queue.poll();
			System.out.print(v + " ");
			
			for(int next : graph[v]) {
				if(!visited[next]) {
					visited[next] = true;
					queue.offer(next);
				}
			}
		}
	}
}              

풀이과정 및 리뷰

우선, 정점(출발점)에 해당하는 숫자의 인덱스에 도착점 정보들을 모아 list로 저장하기 위해

1)List<Integer>[] graph = new ArrayList[N+1] 선언(출발점 == 인덱스 이므로 N+1 만큼 생성)

2)for문 돌며 List타입 배열의 각 인덱스를 초기화해줌

3)시작점과 도착점을 받아 양방향으로 연결해주기 위해 각각 배열의 인덱스 / 리스트로 저장해줌

4)도착점의 숫자가 작은 쪽부터 탐색하기 위해 Collections.sort()

5)방문여부를 판별할 visited 배열을 각 탐색 전 초기화 후 DFS/ BFS 메서드 호출

1. DFS : 깊이우선탐색(Stack or 재귀 로 구현)

   “해당 노드에 방문하는 시점에 방문처리한다.”

   정점 → 도착점(이자 정점) → 도착점(이자 정점) → ….

   노드를 실제 방문해 탐색하는 시점에 방문처리 → 해당 배열의 인덱스에 저장된 리스트(도착점)을 각각 파라미터로 받는 재귀함수 호출

   (시작점에서 도착점으로 계속 타고타고 넘어가므로 우선 한 정점을 깊게 탐색한 후, 더 갈 길이 없다면 재귀함수를 종료하고 되돌아오는 백트래킹 방식)

2. BFS : 너비우선탐색(Queue 로 구현)

   “해당 노드의 인접노드들을 모두 확인해 우선 방문처리하고 큐에 삽입한다.(큐에는 인접노드들 → 인접노드들의 도착점 순서로 삽입되므로, 너비우선탐색이라고도 부른다)”

   정점 1 → 인접노드 2 / 3 / 4 → ….(종료) 정점 2 → 인접노드 3 / 4 → ….

   정점(시작노드)의 인접노드들을 모두 확인해 각각 방문처리 & 큐에 삽입 → 큐에서 노드들을 하나씩 꺼내며 실질적인 탐색이 일어나며, 큐가 빌 때까지 탐색을 반복한다.