[백준] 1260 DFS와 BFS

문제 출처: https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

1. 입력

: 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다.

: 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.

: 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다.

: 입력으로 주어지는 간선은 양방향이다.

2. 출력

: 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다.

: V부터 방문된 점을 순서대로 출력하면 된다.

 

3. 풀이

: 기본적인 DFS, BFS 문제이다.

: 조심해야 할 점은 방문해야 할 정점이 여러개인 경우 정점 번호가 작은 것을 먼저 방문한다는 것이다.

: 이를 위해 처음부터 인접리스트를 각각 정렬해 주면 된다.

: 자연스럽게 방문하는 순서가 작은 것부터 이루어진다.

 

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

public class DFS와BFS {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static int N, M;
	static boolean[] vd, vb;
	static ArrayList<Integer>[] adj;
	public static void main(String[] args) throws Exception{
		st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int start = Integer.parseInt(st.nextToken());
		vd = new boolean[N+1];
		vb = new boolean[N+1];
		adj = new ArrayList[N+1];
		for(int i = 0; i < N+1; i++) {
			adj[i] = new ArrayList<>();
		}
	
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
		
			adj[v1].add(v2);
			adj[v2].add(v1);
		}
		for(int i = 1; i < N+1; i++) {
			Collections.sort(adj[i]);
		}
		dfs(start);
		sb.append("\n");
		bfs(start);
		System.out.println(sb);
	}
	private static void bfs(int start) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(start);
		sb.append(start + " ");
		vb[start] = true;
		
		while(!q.isEmpty()) {
			int cur = q.poll();

			for(int i = 0, size = adj[cur].size(); i < size; i++) {
				int num = adj[cur].get(i);
				if(!vb[num]) {
					sb.append(num + " ");
					vb[num] = true;
					q.offer(num);
				}
			}
		}
		
		
	}
	private static void dfs(int start) {
		vd[start] = true;
		sb.append(start + " ");
		for(int i = 0, size = adj[start].size(); i < size; i++) {
			int cur = adj[start].get(i);
			if(!vd[cur]) dfs(cur);
		}
	}
}