[코딩테스트] 백준 1260 (DFS와 BFS)

문제 설명

 

풀기 전 생각

• Stack과 Queue를 사용하여 DFS, BFS를 구현
• 정점 번호가 작은 것을 먼저 방문하려면 인접리스트를 정렬
• DFS는 Stack을 사용하니 내림차순 정렬
• BFS는 Queue를 사용하니 오름차순 정렬

코드

package algorithm;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class DFSBFS {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int startVertax = sc.nextInt();
        ArrayList<Integer>[] arr = new ArrayList[N + 1];
        boolean[] visitiedByDFS = new boolean[N + 1]; // 방문 체크
        boolean[] visitiedByBFS = new boolean[N + 1];

        for (int i = 1; i < N + 1; i++) { // 각각의 연결리스트 초기화
            arr[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) { // 양방향 연결
            int start = sc.nextInt();
            int end = sc.nextInt();
            arr[start].add(end);
            arr[end].add(start);
        }

        for (int i = 1; i < N + 1; i++) { // 역순 정렬
            Collections.sort(arr[i], Comparator.reverseOrder());
        }

        StringBuilder sb = new StringBuilder();
        StringBuilder sbq = new StringBuilder();

        Stack<Integer> st = new Stack<>();
        st.push(startVertax);
        while (!st.empty()) {
            int value = st.pop(); // 꺼내기
            if (!visitiedByDFS[value]) { // 방문 안되있으면
                sb.append(value + " "); // 출력에 추가
            }
            visitiedByDFS[value] = true;
            for (int a : arr[value]) {
                if (!visitiedByDFS[a]) {
                    st.push(a);
                }
            }
        }

        for (int i = 1; i < N + 1; i++) { // 정렬
            Collections.sort(arr[i]);
        }

        Queue<Integer> qu = new LinkedList();

        qu.add(startVertax);
        visitiedByBFS[startVertax] = true;
        while (!qu.isEmpty()) {
            int value = qu.poll();
            sbq.append(value + " ");
            for (int a : arr[value]) {
                if (!visitiedByBFS[a]) {
                    qu.add(a);
                    visitiedByBFS[a] = true;
                }
            }
        }
        System.out.println(sb.toString());
        System.out.println(sbq.toString());
    }

}

오류 및 개선 

• 통과는 했지만 stack을 사용하면 중복되어 들어가는 경우 발생
• sb.append를 조작하여 통과했지만 불필요한 행위를 함
• dfs와 bfs를 따로 함수로 만들기

좋은 코드

package algorithm;

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Mainzz {
    static int[][] graph;
    static boolean[] visited;

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

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 정점개수
        int M = sc.nextInt(); // 간선개수
        int V = sc.nextInt(); // 시작정점번호

        graph = new int[N + 1][N + 1];

        for (int i = 0; i < M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            // 연결된 노드를 1로 세팅
            graph[a][b] = 1;
            graph[b][a] = 1;
        }
        // node가 1부터 시작하기 때문에 N + 1
        visited = new boolean[N + 1];
        dfs(V);

        System.out.println();

        visited = new boolean[N + 1];

        bfs(V);

        System.out.println();
    }

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

        // j = 1부터 탐색을 하니 정점이 작은 것 부터 검색
        for (int j = 1; j < graph.length; j++) {
            // 연결된 노드인데 방문하지 않은 경우
            if (graph[v][j] == 1 && !visited[j]) {
                // 연결된 노드 찾으면 재귀함수 호출
                dfs(j);
            }
        }
    }

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

        System.out.print(v + " ");

        while (!queue.isEmpty()) {
            int n = queue.poll();

            // 노드 하나로 연결된 노드 먼저 다 체크
            for (int i = 1; i < graph.length; i++) {
                // 연결된 노드인데 방문하지 않은 경우
                if (graph[n][i] == 1 && !visited[i]) {
                    visited[i] = true;
                    System.out.print(i + " ");
                    queue.offer(i);
                }
            }
        }
    }

}

출처: https://tweety1121.tistory.com/entry/백준-1260번-사탕-게임-자바-풀이

참고

• 리스트 형태 vs 배열 형태 풀이가 조금씩 차이
• 재귀함수 vs Stack 풀이가 조금씩 차이

방법을 모두 알고 필요에 맞게 사용하자!