[백준/Java] DFS와 BFS 1260

 

 

문제

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

1260번: DFS와 BFS

 

 

 

 

 

 

 

 

 

풀이

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

public class Main {
    public static StringBuilder sb = new StringBuilder();
    public static boolean[] visited; // 방문 여부
    public static int[][] graph;
    public static int N; // 정점의 개수 (동그라미)
    public static int M; // 간선의 개수 (직선)
    public static int V; // 탐색 시작 번호

    /**
     * 깊이 우선 탐색
     * 
     * @param v
     */
    public void dfs(int v) {
        visited[v] = true;
        System.out.print(v + " ");

        for (int i = 0; i < N + 1; i++) {
            if (graph[v][i] == 1 && visited[i] == false) {
                dfs(i);
            }
        }
    }

    /**
     * 너비 우선 탐색
     * 
     * @param v
     */
    public void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();

        queue.add(v);
        visited[v] = true;

        while (!queue.isEmpty()) {
            int r = queue.poll();
            System.out.print(r + " ");

            for (int i = 1; i < N + 1; i++) {
                if (graph[r][i] == 1 && visited[i] == false) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Main m = new Main();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        graph = new int[N + 1][N + 1];
        visited = new boolean[N + 1];

        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[a][b] = 1;
            graph[b][a] = 1;
        }

        Arrays.fill(visited, false);
        m.dfs(V);
        System.out.println("");

        Arrays.fill(visited, false);
        m.bfs(V);

        bw.flush();
        bw.close();
    }
}

 

 

 

 

 

 

정답