[백준] (실버2) DFS와 BFS 1260 (java)

<문제>

그래프를 DFS, BFS 각각의 방법으로 탐색한 결과를 출력하는 프로그램 작성.
입력으로 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000),
탐색을 시작한 정점 번호 V가 주어지며 M개의 줄에 간선이 연결하는 두 정점의 번호가 주어진다.

<나의 풀이>

방법 1) 연결여부를 1로 표현한 2차원 배열

import java.util.*;

public class DFS_BFS_1260_Array {
    static boolean[] visited;    // 기본값 false 로 고정
    static int[][] graph;  // 각 노드의 연결 여부를 표시한 그래프

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int node_num = sc.nextInt();    // 노드의 개수
        int line_num = sc.nextInt();    // 간선의 개수
        int start_num = sc.nextInt();   // 탐색 시작 노드
        graph = new int[node_num + 1][node_num + 1];
        visited = new boolean[node_num + 1];

        // 각 노드에 연결 여부
        for (int i = 0; i < line_num; i++) {
            int index1 = sc.nextInt();
            int index2 = sc.nextInt();
            graph[index1][index2] = 1;
            graph[index2][index1] = 1;
        }
        dfs(start_num);
        System.out.println();
        Arrays.fill(visited, false);    // 안에 값을 전부 false 로 변경
        bfs(start_num);
    }

    private static void dfs(int start_num) {
        visited[start_num] = true; // 노드 방문 처리
        System.out.print(start_num + " ");
        // 해당 노드의 연결여부와 방문 여부 확인
        for (int i = 1; i < graph[start_num].length; i++) {
            if (graph[start_num][i] == 1 && !visited[i]) {  // 기준 노드와 연결되어 있지만 탐색 X이면
                dfs(i);
            }
        }
    }

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

        while (!que.isEmpty()) {    // 큐가 빌 때까지 반복
            start_node = que.poll(); // 큐의 값 제거, 기준 노드 설정
            System.out.print(start_node + " ");
            for (int i = 1; i < graph[start_node].length; i++) {
                if (graph[start_node][i] == 1 && !visited[i]) {
                    que.offer(i);
                    visited[i] = true;
                }
            }
        }
    }
}

방법 2) 연결된 노드의 숫자를 저장한 2차원 배열

package backjoon.DFS_BFS;

import java.util.*;

public class DFS_BFS_1260_ArrayList {
    static boolean[] visited;    // 기본값 false 로 고정
    static ArrayList<Integer> [] graph;  // 각 노드의 연결 여부를 표시한 그래프

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int node_num = sc.nextInt();    // 노드의 개수
        int line_num = sc.nextInt();    // 간선의 개수
        int start_num = sc.nextInt();   // 탐색 시작 노드
        visited = new boolean[node_num + 1];
        graph = new ArrayList[node_num + 1];
		
        // 배열 채우기
        for (int i = 1; i <= node_num; i++) {
            graph[i] = new ArrayList<>();
        }
        
        // 배열 안의 배열 값 세팅
        for (int i = 0; i < line_num; i++) {
            int num1 = sc.nextInt();
            int num2 = sc.nextInt();
            graph[num1].add(num2);
            graph[num2].add(num1);
        }

        // 배열 안의 배열 요소를 크기순 정렬
        for (int i = 1; i <= node_num; i++) {
            Collections.sort(graph[i]);
        }

        dfs(start_num);
        System.out.println();
        Arrays.fill(visited, false);    // 안에 값을 전부 false 로 변경
        bfs(start_num);
    }

    private static void dfs(int start_num) {
        // 1. 방문처리
        visited[start_num] = true;
        System.out.print(start_num+" ");
        // 2. 순회돌며 확인하기
        for (int node : graph[start_num]) {
            // 3. 미방문시 재귀호출
            if (!visited[node]) {
                dfs(node);
            }
        }
    }

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

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

            for (int node : graph[start_node]) {
                if (!visited[node]) {
                    queue.add(node);
                    visited[node] = true;
                }
            }
        }
    }
}

<핵심 개념>

DFS와 BFS의 실행 순서 차이가 있음.

<피드백>

이차원 배열 ArrayList 쓸 때 문법이 조금 서툴렀음.
코딩테스트 볼 때도 헷갈렸던 경우가 있으니 사용법 다시 공부하기.