백준(baekjoon) [JAVA] - 1260번: DFS와 BFS

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

1260번: DFS와 BFS

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

// DFS와 BFS
public class _1260 {
    public static boolean[] visit;
    public static Queue<Integer> queue = new LinkedList<>();

    public static void dfs(boolean[][] graph, int n, int v) {
        visit[v] = true;
        System.out.print(v + " ");
        for (int i = 1; i <= n; i++) {
            if (!visit[i] && graph[v][i] == true) {
                dfs(graph, n, i);
            }
        }
    }

    public static void bfs(boolean[][] graph, int n, int v) {
        queue.add(v);
        visit[v] = true;
        while (!queue.isEmpty()) {
            int data = queue.poll();
            System.out.print(data + " ");
            for (int i = 1; i <= n; i++) {
                if (!visit[i] && graph[data][i] == true) {
                    visit[i] = true;
                    queue.add(i);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int v = sc.nextInt();

        visit = new boolean[n + 1];
        boolean[][] graph = new boolean[n + 1][n + 1];
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph[a][b] = true;
            graph[b][a] = true;
        }

        dfs(graph, n, v);

        System.out.println();
        for (int i = 0; i <= n; i++) {
            visit[i] = false;
        }

        bfs(graph, n, v);
    }
}

---

MEMO

-- DFS와 BFS의 개념이해가 있다면 쉽게 해결 가능한 문제

-- 재귀를 이용한 DFS방식, 자료구조 QUEUE를 이용한 BFS 방식

 

!! 기본이 가장 중요 !!