백준 1260번 DFS와 BFS

알고리즘은 안한지 너무 오래됐다... 다시 DFS와 BFS부터 시작한다...

 

자 입력을 받으면 DFS 탐색 결과와 BFS 탐색 결과를 출력하면 된다. 

 

이때 중요한 조건은:

1. 방문할 수 있는 정점이 여러 개 일 때 번호가 작은 것부터 방문해야 한다. 

2. 간선은 양방향이다. 

 

이 정도인 것 같다. 

 

답은 맨 아래에 있고 지금부터는 코드를 위에서부터 차근차근 설명할 것이다. 

 

일단 static 으로 빼둘 것들 부터 빼 놓는다. BFS 와 DFS 메서드를 따로 만들거고 거기에 각각 쓰이는 애들이라 전역 변수로 선언하는 것이 번거롭지 않고 편하다. 

public class DFS와BFS_1260 {
    static int N;
    static int M;
    static int V;
    static List<List<Integer>> graph;
    static boolean[] visited;

 

입력을 받는다. 

인접리스트로 구현하는 것이 가장 간결해서 인접 리스트로 채택했다. 

    public static void main(String[] args) throws IOException {
        graph = new ArrayList<>();
        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());

        for(int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        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.get(a).add(b);
            graph.get(b).add(a); // 양방향이니까
        }

작은 수부터 방문을 해야 해서 list 안에 있는 list 는 정렬을 할거다. 

        // 작은 수부터 정렬하라고 명시됨.
        for (int i = 0; i <= N; i++) {
            Collections.sort(graph.get(i));
        }

이제 dfs, bfs 를 호출해두고 메서드를 작성하자

        // dfs 
        visited = new boolean[N + 1];
        dfs(V);
        System.out.println();

        // bfs
        visited = new boolean[N + 1];
        bfs(V);

dfs 는 간결하게 재귀로 구현했다. 

private static void dfs(int curr) {
        visited[curr] = true;
        System.out.print(curr + " ");

        for(int child : graph.get(curr)){
            if(!visited[child]){
                dfs(child);
            }
        }
    }

}

bfs 는 queue로 깔끔하게 구현하고 

    private static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;

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

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

 

 

완성된 코드 

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

public class DFS와BFS_1260 {
    static int N;
    static int M;
    static int V;
    static List<List<Integer>> graph;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        graph = new ArrayList<>();
        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());

        for(int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        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.get(a).add(b);
            graph.get(b).add(a);
        }

        // 작은 수부터 정렬하라고 명시됨.
        for (int i = 0; i <= N; i++) {
            Collections.sort(graph.get(i));
        }
        
        // dfs 
        visited = new boolean[N + 1];
        dfs(V);
        System.out.println();

        // bfs
        visited = new boolean[N + 1];
        bfs(V);



    }

    private static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;

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

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

    private static void dfs(int curr) {
        visited[curr] = true;
        System.out.print(curr + " ");

        for(int child : graph.get(curr)){
            if(!visited[child]){
                dfs(child);
            }
        }
    }

}

 

 

이제 차근차근 다시 알고리즘 풀어가야지...