[BOJ] 1260. DFS와 BFS

 

DFS와 BFS의 기초를 다질 수 있는 문제로서 다양한 풀이 방법을 적용해보았다.

 

 

문제

 

 

입력 예제

 

 

문제 풀이

 

인접 리스트 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ1260 {
    static int n, m, v;
    static ArrayList<Integer>[] arr;
    static boolean[] dfsVisited;
    static boolean[] bfsVisited;
    static String dfsOrder;
    static String bfsOrder;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());

        arr = new ArrayList[n+1];
        dfsVisited = new boolean[n+1];
        bfsVisited = new boolean[n+1];
        dfsOrder = "";
        bfsOrder = "";

        for (int i=1; i<=n; i++) {
            // 인접 리스트 초기화
            arr[i] = new ArrayList<Integer>();
        }

        for (int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            arr[x].add(y);
            arr[y].add(x);

            // 오름차순 정렬
            Collections.sort(arr[x]);
            Collections.sort(arr[y]);
        }

        DFS(v);
        BFS(v);
        System.out.println(dfsOrder);
        System.out.println(bfsOrder);
    }

    public static void DFS(int index) {
        dfsOrder += index + " ";
        if (dfsVisited[index]) {
            return;
        }
        dfsVisited[index] = true;
        for (int i: arr[index]) {
            if (!dfsVisited[i]) {
                DFS(i);
            }
        }
    }

    public static void BFS(int node) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);
        bfsVisited[node] = true;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            bfsOrder += curr + " ";

            for (int i: arr[curr]) {
                // 방문 조건 : 현재 노드와 다음 노드가 연결된 상태이고 아직 방문하지 않은 상태일 때
                if (!bfsVisited[i]) {
                    bfsVisited[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}

 

 

 

Graph 형식 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ1260_ArrayList {
    static int n, m, v;
    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> graph;
    static String dfsOrder;
    static String bfsOrder;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());

        dfsOrder = "";
        bfsOrder = "";
        graph = new ArrayList<>();
        visited = new boolean[n+1];

        for (int i=0; i<=n; i++) {
            // 그래프 초기화
            graph.add(new ArrayList<>());
        }

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

            // 그래프 간 양방향 연결
            graph.get(x).add(y);
            graph.get(y).add(x);

            Collections.sort(graph.get(x));
            Collections.sort(graph.get(y));

        }

        Arrays.fill(visited, false);
        DFS(v);
        System.out.println(dfsOrder);
        Arrays.fill(visited, false);
        BFS(v);
        System.out.println(bfsOrder);
    }

    public static void DFS(int node) {
        visited[node] = true;
        dfsOrder += node + " ";
        for (int i: graph.get(node)) {
            if (!visited[i]) {
                DFS(i);
            }
        }
    }

    public static void BFS(int node) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);
        visited[node] = true;

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            bfsOrder += curr + " ";

            for (int i: graph.get(curr)) {
                if (!visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}

 

 

 

 

인접 행렬 풀이

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

public class BOJ1260_Array {

    static int n, m, v;
    static int[][] arr;
    static boolean[] visited;
    static String dfsOrder;
    static String bfsOrder;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());

        arr = new int[n+1][n+1];
        visited = new boolean[n+1];
        dfsOrder = "";
        bfsOrder = "";

        for (int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            // 노드 간 양방향 연결
            arr[x][y] = arr[y][x] = 1;
//            System.out.println("arr check:" + Arrays.toString(arr[x]));
        }

        Arrays.fill(visited, false);
        DFS(v);
        System.out.println(dfsOrder);
        Arrays.fill(visited, false);
        BFS(v);
        System.out.println(bfsOrder);
    }

    public static void DFS(int node) {
        visited[node] = true;
        dfsOrder += node + " ";
        for (int i=1; i<=n; i++) {
            // 방문 조건: 서로 양방향으로 연결되어 있고, 이미 방문하지 않은 곳
            if (arr[node][i] == 1 && !visited[i]) {
                DFS(i);
            }
        }
    }
    public static void BFS(int node) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(node);
        visited[node] = true;
        bfsOrder += node + " ";

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (int i=1; i<=n; i++) {
                if (arr[curr][i] == 1 && !visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                    bfsOrder += i + " ";
                }
            }
        }
    }
}