[BOJ] 백준 1260 DFS와 BFS

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

 Input 

4 5 1

1 2

1 3

1 4

2 4

3 4

 

 Output 

1 2 4 3
1 2 3 4

4개의 정점과 5개의 간선은 아래와 같은 상태입니다.　

DFS, BFS 방문 순서는 다음과 같습니다.

[구현]

① 그래프 정보를 바탕으로 인접행렬 구현

② 인접행렬에서 DFS, BFS 구현

 Input 

7 6 1

1 4

1 3

1 2

4 6

4 5

2 7

 

 Output 

1 2 7 3 4 5 6
1 2 3 4 7 5 6

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
 
public class Main {
    public static void main(String[] args) {
         
        Scanner sc = new Scanner(System.in);
         
        int N = Integer.parseInt(sc.next());
        int M = Integer.parseInt(sc.next());
        int V = Integer.parseInt(sc.next());
         
        int[][] arr = new int[N+1][N+1];
         
        for(int i=0; i<M; i++) {
            int x = Integer.parseInt(sc.next());
            int y = Integer.parseInt(sc.next());
            arr[x][y] = 1; arr[y][x] = 1;
        }
         
        DFS(arr, V);
        System.out.println();
        BFS(arr, V);
             
    }
 
    private static void BFS(int[][] arr, int v) {
        Queue<Integer> queue = new LinkedList<>();
         
        // 방문한 정점들을 저장한 배열
        boolean[] visited = new boolean[arr.length+1];
        queue.add(v);
        visited[v] = true;
         
        while(!queue.isEmpty()) {
            int cur_v = queue.poll(); // 자료구조 큐에서 Dequeue과 같은 기능
            System.out.print(cur_v + " ");
             
            // 해당 정점에서 방문할 수 있는 모든 정점 방문
            // 번호가 낮은 순대로
            for(int i=1; i<arr.length; i++) {
                // 간선이 존재하고 지금까지 방문하지 않았던 정점을
                if(arr[cur_v][i] == 1 && !visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }
 
    private static void DFS(int[][] arr, int v) {
        Stack<Integer> stack = new Stack<>();
         
        // 방문한 정점들을 저장한 배열
        boolean[] visited = new boolean[arr.length+1];
                 
        stack.push(v); // 시작할 정점
        visited[v] = true; // 시작점 = 해당 정점 방문
        System.out.print(stack.peek() + " ");
         
        // stack 안이 비워질 때 까지
        while(!stack.isEmpty()) {
             
            int cur_v = stack.peek(); // 탐색하고 있는 정점
            boolean isMove = false; // DFS 탐색 도중 back없이 계속해서 탐색되고 있는지 check
             
            // 번호가 낮은 정점부터 확인
            for(int i=1; i<arr.length; i++) {
                // 해당 점점과 간선이 존재하며, 방문한 적이 없어야 한다.
                if(arr[cur_v][i] == 1 && !visited[i]) {
                    visited[i] = true; // 정점 방문 표시
                    stack.push(i);
                    System.out.print(stack.peek() + " ");
                    isMove = true;
                    cur_v = i; // 새롭게 탐색이 진행되고 있는 정점
                    break;
                }
            }
            if(!isMove) { // DFS 도중 back이 필요하다면...
                stack.pop();
            }
        }
    }
}