[JAVA] 백준 1260 (DFS, BFS)

 

 

1260번: DFS와 BFS

 

문제

간선이 주어졌을 때 너비 우선 탐색과 깊이 우선 탐색의 결과 값을 구하시오.

단, 여러 정점으로 방문할 수 있다면 작은 값부터 방문하세요

풀이

먼저 값을 받아줍니다.

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

        int N = Integer.parseInt(st.nextToken()+1);
        int M = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());

        V = new boolean[N];
        A = new ArrayList[N];
        for(int i=1; i<N; i++){
            A[i] = 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());
            A[x].add(y);
            A[y].add(x);
        }

N : 정점의 갯수

M : 주어지는 간선의 수

start : 탐색을 시작하는 정점

A[] : 각 정점이 연결된 정점

V[] : 정점의 방문 여부

간선의 방향이 없기 때문에 양쪽 모두에 담아주었습니다.

for(int i=1; i<N; i++){
      Collections.sort(A[i]);
}

작은 정점부터 방문해야하기 때문에 연결된 정점을 정렬합니다.

DFS

private static void DFS(int index){
        if(V[index]) return ;

        sb.append(index).append(" ");
        V[index] = true;
        for(int x : A[index]){
            if(!V[x])
                DFS(x);
        }

    }

재귀 DFS를 구현하였고 각 정점에 방문할 때 마다 StringBuilder에 값을 기록했습니다.

BFS

 private static void BFS(int index){
        Queue<Integer> q = new LinkedList<>();
        sb.append(index).append(" ");
        V[index] = true;
        q.offer(index);
        while (!q.isEmpty()){
            int now = q.poll();
            for(int x : A[now]){
                if(!V[x]){
                    sb.append(x).append(" ");
                    q.add(x);
                    V[x] = true;
                }
            }
        }
    }

반복을 통해서 구현하였고 시작 정점을 기록하고 정점과 연결된 정점을 큐에 담을 때 마다 StringBuilder에 기록하였습니다.

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

class Main {
    static ArrayList<Integer>[] A;
    static boolean[] V;
    static StringBuilder sb;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken()+1);
        int M = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());

        V = new boolean[N];
        A = new ArrayList[N];
        for(int i=1; i<N; i++){
            A[i] = 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());
            A[x].add(y);
            A[y].add(x);
        }

        for(int i=1; i<N; i++){
            Collections.sort(A[i]);
        }

        sb = new StringBuilder();

        DFS(start);
        V = new boolean[N];
        sb.append("\n");
        BFS(start);
        System.out.println(sb);
    }

    private static void DFS(int index){
        if(V[index]) return ;

        sb.append(index).append(" ");
        V[index] = true;
        for(int x : A[index]){
            if(!V[x])
                DFS(x);
        }

    }

    private static void BFS(int index){
        Queue<Integer> q = new LinkedList<>();
        sb.append(index).append(" ");
        V[index] = true;
        q.offer(index);
        while (!q.isEmpty()){
            int now = q.poll();
            for(int x : A[now]){
                if(!V[x]){
                    sb.append(x).append(" ");
                    q.add(x);
                    V[x] = true;
                }
            }
        }
    }

}

결과