DFS와 BFS

구해야 하는 것

  • 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과

주어진 자료

  • 정점 개수 = N
  • 간선 개수 = M
  • 탐색 시작할 정점 번호 = V
  • 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있음
  • 입력으로 주어지는 간선은 양방향

조건

  • 1 ≤ N ≤ 1,000
  • 1 ≤ M ≤ 10,000

계획

dfs

  1. 간선을 저장할 인접 행렬 arr을 만든다.
  2. 간선이 연결하는 두 정점 번호가 주어지면 arr[v1][v2]에 1을 넣는다.
  3. V를 스택에 넣고 방문 처리를 한다.
  4. 스택 최상단 노드를 꺼내서 방문 처리 됐는지 확인한다.
  5. 방문 처리 안 됐으면 최상단 노드의 인접 노드 중 방문하지 않은 인접 노드를 스택에 넣고 방문 처리를 한다.
  6. 방문하지 않은 인접 노드가 없으면 최상단 노드를 꺼낸다.
  7. 스택이 비면 끝

bfs

  1. V를 큐에 넣고 방문 처리를 한다.
  2. 큐에서 노드 꺼내서 해당 노드의 인접 노드 중 방문하지 않은 노드를 전부 큐에 삽입하고 방문 처리
  3. 큐가 비면 끝

실행

public void solution() throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    // n, m, v 입력
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());

    // 간선 표시
    int[][] arr = new int[n + 1][n + 1];
    for(int i = 0; i < m; i++) {
        st = new StringTokenizer(br.readLine(), " ");
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());
        arr[v1][v2] = 1;
        arr[v2][v1] = 1;
    }

    Stack<Integer> stack = new Stack<>();
    int[] visited = new int[n + 1]; // 방문 여부 저장
    Stack<Integer> dfs = new Stack<>(); // dfs 탐색 결과

    // v를 스택에 넣고 방문 처리
    stack.push(v);
    dfs.push(v);
    visited[v] = 1;

    while(!stack.isEmpty()) {
        int top = stack.peek(); // 최상단 노드

        int near = 0;
        for(int i = 1; i <= n; i++) {
            if((arr[top][i] == 1 || arr[i][top] == 1) &&
                    visited[i] == 0) {
                near = i; // 최상단 노드의 인접 노드
                stack.push(near); // 스택에 넣고
                dfs.push(near); // dfs 탐색 결과에 추가
                visited[near] = 1; // 방문 처리
                break;
            }
        }
        if(near == 0) { // 인접 노드 없으면
            stack.pop();
        }
    }

    // dfs 탐색 결과 출력
    Stack<Integer> result = new Stack<>();
    while(!dfs.isEmpty()) {
        result.push(dfs.pop());
    }
    while(!result.isEmpty()) {
        System.out.print(result.pop() + " ");
    }
    System.out.println();

    // bfs
    Queue<Integer> queue = new LinkedList<>();
    visited = new int[n + 1];
    Stack<Integer> bfs = new Stack<>(); // bfs 탐색 결과

    queue.add(v);
    visited[v] = 1;
    bfs.push(v);

    while(!queue.isEmpty()) {
        int front = queue.peek();

        int near = 0;
        for(int i = 1; i <= n; i++) {
            if(arr[front][i] == 1 && visited[i] == 0) {
                near = i; // 인접 노드
                queue.add(near); // 큐에 넣고
                bfs.push(near); // bfs 탐색 결과에 추가
                visited[near] = 1; // 방문 처리
                break;
            }
        }
        if(near == 0) { // 인접 노드 없으면
            queue.remove();
        }
    }

    // bfs 탐색 결과 출력
    result = new Stack<>();
    while(!bfs.isEmpty()) {
        result.push(bfs.pop());
    }
    while(!result.isEmpty()) {
        System.out.print(result.pop() + " ");
    }
}