[백준] no1260: DFS와 BFS

문제

주어진 Node와 Edge로 이루어진 그래프에 대해 DFS와 BFS로 각각 결과를 구하기

 

문제링크 : https://www.acmicpc.net/problem/1260

---

원리

DFS : 깊이 우선 탐색으로, 주어진 시작 Node로부터 끝까지 갈수 있는 곳까지 구하고, 그 다음으로 넘어가는 방식

BFS : 너비 우선 탐색으로. 주어진 시작 Node로부터 시작하여 같은 depth에 있는 Node들부터 하나씩 추가하는 방식

---

풀이방법

 

---

나의 코드

1. 실패코드 [ 83%에서 실패 -> DFS의 반복문에서 문제 발생 ]

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

    private static int node;
    private static int edge;
    private static int[][] matrix;
    private static boolean[] visitedDFS;
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    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());
        edge = Integer.parseInt(st.nextToken());
        matrix = new int[node + 1][node + 1];
        int start = Integer.parseInt(st.nextToken());

        for (int i = 0; i < edge; i++) {
            StringTokenizer tempSt = new StringTokenizer(br.readLine(), " ");
            int node1 = Integer.parseInt(tempSt.nextToken());
            int node2 = Integer.parseInt(tempSt.nextToken());
            matrix[node1][node2] = matrix[node2][node1] = 1; // 양방향 체크
        }

        visitedDFS = new boolean[node + 1];
        for (int i = start; i <= node; i++) {
            if (!visitedDFS[i]) DFS(i);
        }

        bw.write("\n");

        BFS(start);

        bw.close();
    }

    /**
     * DFS 로 탐색
     */
    private static void DFS(int start) throws IOException {
        visitedDFS[start] = true;
        bw.write("" + start + " ");

        for (int i = 1; i <= node; i++) {
            if (matrix[start][i] == 1 && !visitedDFS[i]) {
                DFS(i);
            }
        }
    }


    /**
     * BFS 로 탐색
     */
    private static void BFS(int start) throws IOException {
        Deque<Node> dq = new ArrayDeque<>();
        dq.add(new Node(start));
        boolean[] visitedBFS = new boolean[node + 1];
        visitedBFS[start] = true;

        while (!dq.isEmpty()) {
            Node now = dq.poll();
            int nowD = now.departure;
            bw.write("" + nowD + " ");

            for (int i = 1; i <= node; i++) {
                if (matrix[nowD][i] == 1 && !visitedBFS[i]) {
                    dq.add(new Node(i));
                    visitedBFS[i] = true;
                }
            }
        }
    }

    private static class Node {
        private int departure;
        public Node(int departure) {
            this.departure = departure;
        }
    }
}

 

2. DFS [ 성공 코드 ]

	private static int node;
    private static int edge;
    private static int[][] matrix;
    private static boolean[] visitedDFS;
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        visitedDFS = new boolean[node + 1];
        DFS(start);
        bw.close();
    }

    private static void DFS(int start) throws IOException {
        visitedDFS[start] = true;
        bw.write("" + start + " ");

        for (int i = 1; i <= node; i++) {
            if (matrix[start][i] == 1 && !visitedDFS[i]) {
                DFS(i);
            }
        }
    }

 

3. BFS [ 성공 코드 ]

	private static int node;
    private static int edge;
    private static int[][] matrix;
    private static boolean[] visitedDFS;
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        BFS(start);
        bw.close();
    }
    
    private static void BFS(int start) throws IOException {
        Deque<Integer> dq = new ArrayDeque<>();
        dq.add(start);
        boolean[] visitedBFS = new boolean[node + 1];
        visitedBFS[start] = true;

        while (!dq.isEmpty()) {
            int now = dq.poll();
            bw.write("" + now + " ");

            for (int i = 1; i <= node; i++) {
                if (matrix[now][i] == 1 && !visitedBFS[i]) {
                    dq.add(i);
                    visitedBFS[i] = true;
                }
            }
        }
    }

 

4. 전체 코드 [ 성공 코드 ]

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class no1260 {

    private static int node;
    private static int edge;
    private static int[][] matrix;
    private static boolean[] visitedDFS;
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    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());
        edge = Integer.parseInt(st.nextToken());
        matrix = new int[node + 1][node + 1];
        int start = Integer.parseInt(st.nextToken());

        for (int i = 0; i < edge; i++) {
            StringTokenizer tempSt = new StringTokenizer(br.readLine(), " ");
            int node1 = Integer.parseInt(tempSt.nextToken());
            int node2 = Integer.parseInt(tempSt.nextToken());
            matrix[node1][node2] = matrix[node2][node1] = 1; // 양방향 체크
        }

        visitedDFS = new boolean[node + 1];
        DFS(start);

        bw.write("\n");

        BFS(start);

        bw.close();
    }

    /**
     * DFS 로 탐색
     */
    private static void DFS(int start) throws IOException {
        visitedDFS[start] = true;
        bw.write("" + start + " ");

        for (int i = 1; i <= node; i++) {
            if (matrix[start][i] == 1 && !visitedDFS[i]) {
                DFS(i);
            }
        }
    }


    /**
     * BFS 로 탐색
     */
    private static void BFS(int start) throws IOException {
        Deque<Integer> dq = new ArrayDeque<>();
        dq.add(start);
        boolean[] visitedBFS = new boolean[node + 1];
        visitedBFS[start] = true;

        while (!dq.isEmpty()) {
            int now = dq.poll();
            bw.write("" + now + " ");

            for (int i = 1; i <= node; i++) {
                if (matrix[now][i] == 1 && !visitedBFS[i]) {
                    dq.add(i);
                    visitedBFS[i] = true;
                }
            }
        }
    }
}

---

레퍼런스 코드

참고 링크 : https://m.blog.naver.com/lm040466/221787478911