[백준 1260번] DFS와 BFS

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

1260번: DFS와 BFS

문제 풀이 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class baekjoon1260 {
	static List<ArrayList<Integer>> graph = new ArrayList<>(); // 인접리스트 그래프
	static boolean[] visited; // 방문 여부 배열
	static List<Integer> bfslist = new ArrayList<>(); // bfs 노드를 저장할 리스트
	static List<Integer> dfslist = new ArrayList<>(); // dfs 노드를 저장할 리스트

	public static void main(String[] args) throws IOException {
		// DFS와 BFS
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken()); // 정점의 개수
		int M = Integer.parseInt(st.nextToken()); // 간선의 개수
		int V = Integer.parseInt(st.nextToken()); // 탐색을 시작할 정점의 번호

		visited = new boolean[N + 1];

		for (int i = 0; i <= N; i++) {
			graph.add(new ArrayList<Integer>());
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());

			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());

			// 양방향 그래프 세팅
			graph.get(a).add(b);
			graph.get(b).add(a);
		}

		// 그래프 오름차순 정렬
		for (int i = 1; i <= N; i++) {
			Collections.sort(graph.get(i));
		}

		bfs(V);

		visited = new boolean[N + 1];

		dfs(V);

		for (int i = 0; i < bfslist.size(); i++) {
			System.out.print(dfslist.get(i) + " ");
		}
		System.out.println();

		for (int i = 0; i < bfslist.size(); i++) {
			System.out.print(bfslist.get(i) + " ");
		}
	}

	private static void bfs(int num) {
		Queue<Integer> queue = new LinkedList<>();

		queue.offer(num);
		visited[num] = true;

		while (!queue.isEmpty()) {
			int cur = queue.poll();

			bfslist.add(cur);

			for (Integer next : graph.get(cur)) {
				if (visited[next] == false) {
					visited[next] = true;
					queue.offer(next);
				}
			}
		}
	}

	private static void dfs(int num) {
		visited[num] = true;
		dfslist.add(num);
		for (Integer next : graph.get(num)) {
			if (visited[next] == false) {
				dfs(next);
			}
		}
	}

}

 

주요 핵심 포인트

1. 위 문제는 BFS와 DFS의 기본을 알고 있는지를 묻는 문제로 개념적인 공부가 필요하다.

2. 출력값은 오름 차순을 기준으로 뽑아야 하기 때문에 그래프의 리스트를 오름차순으로 정렬하였다.

3. bfs 함수의 경우 큐를 사용하여 기본적인 bfs 함수를 갖추었고, 출력하고자 하는 값을 bfslist에 순서대로 저장하였다.

4. dfs 함수의 경우도 dfs의 기본 원리에 맞춰서 깊이 탐색을 진행하였다.

 

개선해야할 사항

: bfs와 dfs의 값을 출력하기 위하여 리스트를 선언하였으나, 리스트가 아니라 출력을 사용하여 푸는 방법도 있을 듯하다. 필자는 main에서 값을 출력하는 것을 선호하여 리스트로 만들었지만, 함수에서 print() 처리를 하는 방법도 생각해보아야 겠다.