[백준] 1260 DFS와 BFS - Graph Theory / Java

• 문제 링크

1260번: DFS와 BFS

 

• 풀이 과정

간선 정보 저장 시 인접 리스트는 시간복잡도 O(V^2), 인접 행렬은 시간 복잡도 O(V+E) 이므로 인접 리스트를

사용하여 풀이하였다.

 

간선 정보 저장시 양방향으로 저장하고 분기가 있을 경우 정점 번호가 낮은 정점부터 방문하므로 각각 정렬을 수행한다.

방문 정보를 저장할 check 배열은 DFS, BFS 순으로 메소드가 수행될 때마다 초기화 해준다.

 

우선 DFS 의 탐색 과정은 이번에 방문한 노드를 check 배열에 true 값으로 저장하고

이 노드에 연결된 방문하고자 하는 인접 노드 중 방문하지 않은 노드로 이동을 재귀 함수로 구현해

소위 한 우물만 파는 형태인 깊이 우선 탐색을 진행하며 이는 Stack 으로도 구현 가능하다.

 

BFS의 탐색 과정은 시작 노드를 Queue 연결 리스트에 삽입 후 check 배열에 true 값으로 저장하고

큐가 비어있을 때까지 반복하는 while 문에서 탐색이 시작된다.

큐에서 poll (FIFO) 한 값이 방문한 노드가 되며 이 노드를 기준 인접한 노드의 방문 여부를 탐색 후 큐에 삽입해

앞서 큐에 저장된 값들이 poll 되기까지 대기시켜 너비 우선 탐색을 진행한다.

 

이렇게 각 탐색과정에서 노드 값들을 StringBuilder 에 저장해 각각의 탐색한 결과가 출력된다.

 

• 풀이 코드

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

public class Main {

	static StringBuilder sb = new StringBuilder();
	static ArrayList<ArrayList<Integer>> list;
	static boolean[] visit;

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int v = Integer.parseInt(st.nextToken());

		list = new ArrayList<>();
		for (int i = 0; i < n + 1; i++)
			list.add(new ArrayList<>());

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());

			list.get(y).add(x);
			list.get(x).add(y);
		}

		for (int i = 1; i <= n; i++)
			Collections.sort(list.get(i));

		visit = new boolean[n + 1];
		dfs(v);
		sb.append("\n");

		visit = new boolean[n + 1];
		bfs(v);

		bw.write(sb + "\n");
		bw.flush();
	}

	private static void dfs(int node) {
		if (visit[node])
			return;

		visit[node] = true;
		sb.append(node + " ");

		for (int i : list.get(node)) {
			if (!visit[i])
				dfs(i);
		}
	}

	private static void bfs(int node) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(node);
		visit[node] = true;

		while (!q.isEmpty()) {
			int now = q.poll();
			sb.append(now + " ");

			for (int i : list.get(now)) {
				if (!visit[i]) {
					visit[i] = true;
					q.offer(i);
				}
			}
		}
	}

}