[백준][Java] 1260번 : DFS와 BFS

[문제 링크]

https://www.acmicpc.net/problem/1260

---

문제 설명

• 그래프를 DFS, BFS로 탐색한 결과 출력
• 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문
• 더 이상 방문할 수 있는 점이 없는 경우 종료
• 입력: 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V, 간선이 연결하는 두 정점의 번호
• 출력: DFS 수행결과, BFS 수행 결과

 

 

 

문제 풀이

• DFS는 재귀를 사용해서 구현
• BFS는 큐를 사용해서 구현

(1) Array 2차원 배열 사용

import java.io.*;
import java.util.*;

public class Main {
    public static int n, m, v;
    public static boolean[] visited;   //방문 처리 배열
    public static int[][] graph;	//Array 2차원 배열 사용
    public static Queue<Integer> q = new LinkedList<>();

    public static void dfs(int v) {
        visited[v] = true;  //현재 정점 방문 처리
        System.out.print(v + " ");

        for (int i = 1; i <= n; i++) {
            if (graph[v][i] == 1 && !visited[i]) {  //방문하지 않은 노드일 경우
                dfs(i);
            }
        }
    }

    public static void bfs(int v) {
        visited[v] = true;  //현재 정점 방문 처리
        q.offer(v);

        //큐가 빌 때까지 실행
        while (!q.isEmpty()) {
            int x = q.poll();
            System.out.print(x + " ");

            for (int i = 1; i <= n; i++) {
                if (graph[x][i] == 1 && !visited[i]) {  //방문하지 않은 노드일 경우
                    q.offer(i);
                    visited[i] = true;
                }
            }
        }
    }

     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());  //탐색 시작 번호

         graph = new int[n+1][n+1];
         for (int i = 0; i < m; i++) {
             StringTokenizer st1 = new StringTokenizer(br.readLine());
             int x = Integer.parseInt(st1.nextToken());
             int y = Integer.parseInt(st1.nextToken());
             graph[x][y] = graph[y][x] = 1; //양방향
         }

         visited = new boolean[n + 1];
         dfs(v);
         System.out.println();
         visited = new boolean[n + 1];
         bfs(v);
    }
}

 

 

 

(2) ArrayList 2차원 배열 사용

import java.io.*;
import java.util.*;

public class Main {
    public static int n, m, v;
    public static boolean[] visited;
    public static ArrayList<Integer>[] graph;   //ArrayList 2차원 배열 사용
    public static Queue<Integer> q = new LinkedList<>();

    public static void dfs(int v) {
        visited[v] = true;  //현재 정점 방문 처리
        System.out.print(v + " ");

        for (Integer i : graph[v]) {
            if (!visited[i]) {
                dfs(i);
            }
        }
    }

    public static void bfs(int v) {
        visited[v] = true;  //현재 정점 방문 처리
        q.offer(v);

        //큐가 빌 때까지 실행
        while (!q.isEmpty()) {
            int x = q.poll();
            System.out.print(x + " ");


            for (Integer i : graph[x]) {
                if (!visited[i]) {  //방문하지 않은 노드일 경우
                    q.offer(i);
                    visited[i] = true;
                }
            }
        }
    }

     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());  //탐색 시작 번호

         graph = new ArrayList[n + 1];

         for (int i = 0; i <= n; i++) {
             graph[i] = new ArrayList<>();
         }

         for (int i = 0; i < m; i++) {
             StringTokenizer st1 = new StringTokenizer(br.readLine());
             int x = Integer.parseInt(st1.nextToken());
             int y = Integer.parseInt(st1.nextToken());
             graph[x].add(y);
             graph[y].add(x); //양방향
         }

         //방문가능한 정점이 여러개일 경우, 번호가 작은 것부터 먼저 방문하기 위해 오름차순 정렬
         for (ArrayList<Integer> list : graph) {
             Collections.sort(list);
         }

         visited = new boolean[n + 1];
         dfs(v);
         System.out.println();
         visited = new boolean[n + 1];
         bfs(v);
    }
}