[boj 1260][Java] DFS와 BFS

주의사항

(1) StringBuillder 이용하여 출력하는 방법
(2) Stack, Queue 의 구현 방법
- 스택: Deque<Integer> stack = new ArrayDeque<Integer>();
- 큐: Queue<Integer> q = new LinkedList<>();

코드

// boj 1260 DFS 와 BFS  - Java Ver.

import java.io.*;
import java.util.*;

public class Main {

	static StringBuilder sb = new StringBuilder();

    // 전역으로 선언
    static boolean[] visited; // 1<=n<=1000
    static int[][] graph;
    // 연결리스트 버전: LinkedList<Integer>[] graph;

    static int n, m, start;

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
    
        n = Integer.parseInt(st.nextToken()); // node 노드수
        m = Integer.parseInt(st.nextToken()); // edge 간선수 
        start = Integer.parseInt(st.nextToken()); // start 정점 번호 

        // 전역 변수 초기화 
        visited = new boolean[n+1];
        graph = new int[n+1][n+1];
        // Java의 경우 크기 할당 시 false, 0 으로 전체 초기화됨 

        // 간선 입력
        for (int i = 0; i < m; i++) {
            StringTokenizer st2 = new StringTokenizer(bf.readLine());
            int a = Integer.parseInt(st2.nextToken());
            int b = Integer.parseInt(st2.nextToken());
            // 양방향 간선 
            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        // BFS, DFS 수행
        // DFS
        dfs1(start);
        sb.append("\n");

        // visited 배열 재 초기화
        visited = new boolean[n+1];

        // bfs
        bfs(start);

        // output
        System.out.println(sb);
        return;
    }

    public static void bfs(int start) {
        // 큐 선언 시 주의사항: int 안되고 박스형 Integer만 가능 
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visited[start] = true;

        while(!q.isEmpty()){
            int v = q.poll();
            sb.append(v + " ");
            //System.out.print(v + " ");

            // 인접노드 모두 방문
            for (int i = 1; i<= n; i++) {
                if (graph[v][i] == 1 && visited[i] == false) {
                    q.add(i);
                    visited[i] = true;
                } 
            }
        }
    }

    // dfs [1] 재귀 
    public static void dfs1(int start) {
        visited[start] = true;
        sb.append(start + " ");

        for (int i=1; i<=n; i++) {
            if (graph[start][i] == 1 && visited[i] == false) {
                dfs1(i);
            }
        }
    }

    // dfs [2] 스택
    public static void dfs2(int start) {
        // Deque 인터페이스 이용 // 초기화 시 Integer 이용용
        Deque<Integer> stack = new ArrayDeque<Integer>();
        stack.push(start);

        while(!stack.isEmpty()) {
            int v = stack.pop();

            if (visited[v]) {
                continue;
            } 
            visited[v] = true;

            sb.append(v + " ");

            // 노드 방문 순서가 숫자 작은거부터 하길 바람 
            // -> 큰거부터 stack 에 넣어야 작은거가 나옴 
            for (int i = n; i>=1; i--) {
                if (graph[v][i] == 1 && !visited[i]) {
                    stack.push(i);  // visited는 여기서 처리 안 함!
                }
            }
        }
    }


}