[백준(Baekjoon)][자바(java)] 1260 : DFS와 BFS / 그래프와 순회

 

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

1260번: DFS와 BFS

 

문제 풀이

 

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 Main {
	
	static List<List<Integer>> edge;
	static boolean visited[];
	static StringBuilder sb = new StringBuilder();
	
	public static void dfs(int u) {
		visited[u] = true;
		sb.append(u + " ");
		for (int v : edge.get(u))
			if (!visited[v])
				dfs(v);
	}
	
	public static void bfs(int r) {
		visited[r] = true;
		Queue<Integer> queue = new LinkedList<>();
		queue.add(r);
		while (!queue.isEmpty()) {
			int u = queue.remove();
			sb.append(u + " ");
			for (int v : edge.get(u)) {
				if (!visited[v]) {
					visited[v] = true;
					queue.add(v);
				}
			}
		}
	}

	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()) + 1,
			m = Integer.parseInt(st.nextToken()),
			r = Integer.parseInt(st.nextToken()), u, v, i;
		edge = new ArrayList<>();
		for (i = 0; i < n; ++i)
			edge.add(new ArrayList<>());
		for (i = 0; i < m; ++i) {
			st = new StringTokenizer(br.readLine());
			u = Integer.parseInt(st.nextToken());
			v = Integer.parseInt(st.nextToken());
			edge.get(u).add(v);
			edge.get(v).add(u);
		}
		br.close();
		
		for (i = 0; i < n; ++i)
			Collections.sort(edge.get(i));
		
		visited = new boolean[n];
		
		dfs(r);
		
		visited = new boolean[n];
		sb.append("\n");
		
		bfs(r);
		
		System.out.println(sb.toString());
	}
}