문제 이해

그래프를 DFS로 탐색한 경우와 BFS로 탐색한 결과를 출력하라.
시작점은 입력값으로 주어진다.

---

문제 풀이

DFS와 BFS같은 경우 개념을 제대로 하지 않으면 절대 풀 수 없다.

따라서, 개념을 제대로 이해하고 문제를 풀어야하며, DFS와 BFS에 대한 문제는 앞으로 왜 DFS나 BFS를 활용했는지에 대해서만 기입할 것이다.

DFS : Stack이나 재귀함수를 통한 구현

BFS : Queue를 통한 구현

---

코드

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

public class Main {
	
	static int N, M;
	static int V;
	static boolean[] visit; 
	static ArrayList<Integer>[] edges;
	static StringBuilder sb = new StringBuilder();
	
	static void dfs(int node) {
		if(visit[node]) return;
		
		visit[node] = true;
		sb.append(node+" ");
		
		for(int s:edges[node]) {
			dfs(s);
		}
	}
	
	static void bfs() {
		Queue<Integer> queue = new LinkedList<>();
		
		queue.add(V);
		while(!queue.isEmpty()) {
			int point = queue.poll();
			
			if(visit[point]) {
				continue;
			}
			sb.append(point+" ");
			visit[point] = true;
			
			for(int s:edges[point]) {
				queue.add(s);
			}
		}
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		N = sc.nextInt();
		M = sc.nextInt();
		V = sc.nextInt();
		
		edges = new ArrayList[N+1];
		visit = new boolean[N+1];
		
		for(int i = 1;i<N+1;i++) {
			edges[i] = new ArrayList<Integer>();
		}

		int a,b;
		for(int i =0;i<M;i++) {
			a = sc.nextInt();
			b = sc.nextInt();
			
			edges[a].add(b);
			edges[b].add(a);
		}
		
		for(int i = 1;i<N+1;i++) {
			Collections.sort(edges[i]);
		}
	
		dfs(V);
		sb.append("\n");
		visit = new boolean[N+1];
		bfs();
		
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 2번째 줄 : Stack 사용, 첫번째 줄 : 재귀함수 사용
  • 재귀함수가 조금 더 빠름