[백준] 1260번 DFS와BFS Java

DFS와 BFS

문제에 친절하게 DFS와 BFS를 사용하라고 알려 줍니다.

DFS

깊이우선탐색으로, 재귀나 스택으로 짤 수 있습니다.
시작노드부터 가깝고 작은 노드부터 탐색하지 않은 곳을 방문하여 탐색합니다.

BFS

넓이우선탐색으로, 큐를 사용하여 짤 수 있다.
시작노드로부터 연결된 모든 간선을 탐색하며 큐에 집어넣고 탐색을 완료하면 큐에서 빼는 방식입니다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
    public static boolean[] visited = new boolean[1001];
    public static int[][] map = new int[1001][1001];
    public static int N;
    public static int M;
    public static int V;

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int first = Integer.parseInt(st.nextToken());
            int second = Integer.parseInt(st.nextToken());
            map[first][second] = 1;
            map[second][first] = 1;
        }

        dfs(V);
        System.out.println();
        bfs(V);
    }

    private static void dfs(int v) {
        visited[v] = true;
        System.out.print(v + " ");
        for(int i = 1; i <= N; i++){
            if(map[v][i] == 1 && visited[i] == false) dfs(i);
        }
    }

    private static void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(v);
        visited[v] = false;

        while(!queue.isEmpty()){
            int tmp = queue.poll();
            System.out.print(tmp + " ");
            for(int i = 1; i <= N; i++){
                if(map[tmp][i] == 1 && visited[i] == true){
                    queue.offer(i);
                    visited[i] = false;
                }
            }
        }
    }
}