[백준] 1260번

bfs는 queue, dfs는 재귀를 활용했다.

 

 

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

public class Main {

    static int node, line, start;
    static int[][] arr;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();

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

        node = Integer.parseInt(st.nextToken());    // 정점의 개수
        line = Integer.parseInt(st.nextToken());    // 간선의 개수
        start = Integer.parseInt(st.nextToken());    // 탐색을 시작할 정점의 번호

        arr = new int[node + 1][node + 1];
        visited = new boolean[node + 1];

        for (int i = 0; i < line; i++) {
            StringTokenizer edge = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(edge.nextToken());
            int y = Integer.parseInt(edge.nextToken());

            arr[x][y] = arr[y][x] = 1;
        }

        dfs(start);
        sb.append("\n");

        visited = new boolean[node + 1];
        bfs(start);

        System.out.println(sb);

    }

    public static void bfs(int v) {
        Queue<Integer> que = new LinkedList<>();
        que.add(v);
        visited[v] = true;

        while (!que.isEmpty()) {
            v = que.poll();	// 큐에서 노드를 꺼낸다
            sb.append(v).append(" ");

            for (int i = 1; i <= node; i++) {
            // 해당 노드와 인접한 노드들 중 아직 방문하지 않은 노드를 큐에 추가하고 방문 처리한다
                if (arr[v][i] == 1 && !visited[i]) {
                    que.add(i);
                    visited[i] = true;
                }
            }
        }
    }

    public static void dfs(int v) {
        visited[v] = true;
        sb.append(v).append(" ");

        for (int i = 0; i <= node; i++) {
        // 해당 노드와 인접한 노드들 중 아직 방문하지 않은 노드들을 재귀 호출한다
            if (arr[v][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }
    }
}