[백준 자바] 1260 DFS와 BFS

 

배웠던 BFS와 DFS 활용하는 문제~~~

 

출력 형태를 맞추느라고 StringBuffer 사용했다.

 

- 첫번째 풀이 (그냥 주르륵 나열/ Stack, Queue 사용) 

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

// DFS와 BFS
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 첫째 줄 정점의 개수 N, 간선의 개수 M, 탐색 시작할 번호 V
        String[] inputs = br.readLine().split(" ");
        int N = Integer.parseInt(inputs[0]); //방문지점 개수
        int M = Integer.parseInt(inputs[1]); //연결다리 개수
        int V = Integer.parseInt(inputs[2]); // 시작번호


        int[][] map = new int[N+1][N+1]; //방문지점과 각 지점의 연결성을 표시하는 맵
        // 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호.
        for(int i=0; i<M; i++) {
            String[] connects = br.readLine().split(" ");

            int start = Integer.parseInt(connects[0]);
            int last = Integer.parseInt(connects[1]);

            map[start][last] = 1;
            map[last][start] = 1;
        } // 맵 완성

        // 첫째줄에는 DFS 결과
        // 1. Stack
        // 2. List 방문한 곳 저장
        // 3. 방문 여부 저장 boolean
        Stack<Integer> toVisit = new Stack<>();
        StringBuffer sb = new StringBuffer();
        boolean[] visited = new boolean[N+1];

        toVisit.push(V); //첫 시작이니 스택에 넣고 시작

        while(!toVisit.empty()) {
            int num = toVisit.pop(); // 꺼낸 것이 확인할 num

            if(visited[num]==true) continue;

            sb.append(num+" ");
            visited[num] =true;

            for(int i=N; i>0; i--) {
                if(map[num][i] == 1 && visited[i]== false) {
                    toVisit.push(i);
                }
            }
        }

        System.out.println(sb);

        // 둘째줄에는 BFS 결과
        Queue<Integer> toVisit2 = new LinkedList<>();
        sb.delete(0, sb.length()); //sb초기화
        visited = new boolean[N+1]; //visited 초기화

        toVisit2.offer(V);

        while(!toVisit2.isEmpty()) {
            int num2 = toVisit2.poll();

            if(visited[num2]==true) continue;

            sb.append(num2+" ");
            visited[num2] = true;

            for(int i=1; i<N+1; i++) {
                if(map[num2][i]==1 && visited[i] == false) {
                    toVisit2.offer(i);
                }
            }
        }
        System.out.println(sb);
    }
}

 

- 두번째 풀이 (메서드로 분리, DFS는 재귀함수 사용, BFS는 큐 사용)

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

// DFS와 BFS
public class Main {
    static int N;
    static int M;
    static int V;
    static StringBuffer sb;
    static boolean[] visited;
    static int[][] map;

    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());

        map = new int[N+1][N+1];
        visited = new boolean[N+1]; //visited 초기화
        sb = new StringBuffer();

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());

            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());

            map[left][right]=1;
            map[right][left]=1;
        }

        dfs(V);
        System.out.println(sb);
        visited = new boolean[N+1]; //visited 초기화
        sb.delete(0, sb.length()); //stringBuffer 초기화
        bfs(V);
        System.out.println(sb);

    }

    public static void dfs(int V){
        visited[V]=true; //들어온 순간 true가 됨.
        sb.append(V+" "); //그 값을 sb에 덧붙임

        for(int i=1; i<=N; i++) { //V와 연결된 것을 찾는다
            if(map[V][i]==1&&!visited[i]){
                dfs(i);
            }
        }
    }

    public static void bfs(int V){
        Queue<Integer> myQueue = new LinkedList<>();

        myQueue.offer(V);

        while(!myQueue.isEmpty()){
            int next = myQueue.poll();

            if(visited[next]) continue;
            sb.append(next+" ");
            visited[next] = true;

            for(int i=1; i<=N; i++) {
                if(visited[i]) continue;
                if (map[next][i] == 1) {
                    myQueue.offer(i);
                }
            }
        }
    }
}

 

 

결과는 위에가 첫번째 풀이, 아래가 두번째 풀이...

메서드 나누고, 재귀함수 사용한 것이 훨씬 빠르다!!!!