https://dingcoding.tistory.com/199

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1
4 5 1
1 2
1 3
1 4
2 4
3 4
예제 출력 1
1 2 4 3
1 2 3 4
예제 입력 2
5 5 3
5 4
5 2
1 2
3 4
3 1
예제 출력 2
3 1 2 5 4
3 1 4 2 5
예제 입력 3
1000 1 1000
999 1000
예제 출력 3
1000 999
1000 999

풀이

package silver2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class B1260_DFS와_BFS {
	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());
		int V = Integer.parseInt(st.nextToken());
		int startNode = Integer.parseInt(st.nextToken());
		Graph g = new Graph(N);

		for (int i = 0; i < V; i++) {
			st = new StringTokenizer(br.readLine());
			int N1 = Integer.parseInt(st.nextToken());
			int N2 = Integer.parseInt(st.nextToken());

			g.makeVertex(N1, N2);
		}
		g.DFS(startNode);
		g.BFS(startNode);
	}
}

class Graph {
	public Map<Integer, ArrayList<Integer>> adjList = new HashMap<>(); // 인접리스트(인접노드들)
	boolean[] visited;

	public Graph(int N) {
		this.visited = new boolean[N + 1]; // 방문검사용 배열
	}

	// N1과 N2간의 Vertex추가
	public void makeVertex(int N1, int N2) {
		// N1 노드가 value로 가지고있는 리스트에 N2추가
		ArrayList<Integer> temp = adjList.get(N1); // n1의 인접노드들

		if (temp == null) // 만약에 비었으면 새로만들기
			temp = new ArrayList<Integer>();

		// 간선만들기
		temp.add(N2);
		adjList.put(N1, temp);
		// ==========================================
		// N2노드가 value로 가지고있는 리스트에 N1추가
		temp = adjList.get(N2); // n1의 인접노드들

		if (temp == null) // 만약에 비었으면 새로만들기
			temp = new ArrayList<Integer>();

		// 간선만들기
		temp.add(N1);
		adjList.put(N2, temp);
	}

	public void DFS(int startNode) {
		// visited초기화 전처리
		Arrays.fill(visited, false);

		Stack<Integer> stack = new Stack<>(); // DFS용 스택

		// 시작 정점 결정
		stack.add(startNode);

		// ================노드 순회 시작=====================
		while (stack.size() != 0) {
			// 스택의 최상단 확인
			int popedNode = stack.pop();
			
			// 미방문 노드일시 방문처리 및 결과에 입력
			if (!visited[popedNode]) {
				visited[popedNode]=true;
				System.out.print(popedNode+" ");
			}

			// 방문 노드의 인접 노드들 검사
			ArrayList<Integer> popedList = adjList.get(popedNode);

			if (popedList != null) {
				Collections.sort(popedList);
				// 방문노드에 인접한 노드들의 리스트를 내림차순 정렬해서 add해야
				// stack에서 오름차순으로 pop할 수 있음
				Collections.reverse(popedList);

				// 인접한 노드 하나 검사
				for (Integer node : popedList) {
					// 방문하지 않은 정점 존재할 시
					if (!visited[node])
						stack.add(node);
				} // 인접한 노드 하나 검사 끝
			} //현재 방문노드의 인접노드 여부검사 끝
		} // 노드 순회 끝 ==================================
		System.out.println();
	} // DFS 끝 ==========================================

	public void BFS(int startNode) {
		// visited초기화 전처리
		Arrays.fill(visited, false);

		Queue<Integer> queue = new LinkedList<>();  //BFS용 큐

		// 시작 정점 결정
		queue.add(startNode);
		visited[startNode] = true;

		// ================노드 순회 시작=====================
		while (queue.size() != 0) {

			// 큐의 맨앞 노드 확인
			int polledNode = queue.poll();
			System.out.print(polledNode+" ");

			// 현재 방문노드의 인접노드가 있는지 검사
			ArrayList<Integer> polledList = adjList.get(polledNode);

			if (polledList != null) {
				// 오름차순으로 노드에 방문해야해서 인접노드 정렬
				Collections.sort(polledList);
				
				// 인접노드 순회
				for (Integer node : polledList) {
					if (!visited[node]) { //방문하지 않은 노드만 enqueue
						queue.add(node);
						visited[node]=true;
					}
				} //인접노드 순회 끝
			} // 방문노드의 인접노드 유무 검사
		} // ================노드 순회 끝 ===================
		System.out.println();
	}//BFS끝
}

설명은 여기로... https://velog.io/@iamjinseo/DFSBFS

결과