1. 문제

문제 설명

그래프가 주어졌을 때 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하는 것이다. DFS와 BFS를 연습할 수 있는 가장 기초적인 문제

제한사항

• 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다
• 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입출력

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

4 5 1
1 2
1 3
1 4
2 4
3 4

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

1 2 4 3
1 2 3 4

2. 아이디어

대놓고 DFS, BFS 가지고 푸세요~ 하는 문제라 DFS와 BFS에 관한 지식을 정리하는 것이 중요할 것 같다.

DFS

DFS(Depth-First Search, 깊이우선탐색)이란,
그래프 탐색을 할 때, 임의의 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게(leaf node까지) 탐색하는 방법이다.

• 모든 노드를 탐색하고 싶을 때 사용한다
• 단순 검색 속도 자체는 BFS에 비해 느리다
• 그래프 탐색할 때 방문한 노드를 기록하고 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다 이를 무시하면 무한루프에 빠질 위험이 있다
• leaf node에 도달했을 때 위에서 실시한 검사와 함께 backtracking을 실시한다
• 구현방법에는 재귀 혹은 스택을 활용하는 방법이 있는데 재귀를 활용하는 방식이 더 편리하여 많이 쓰이고 있다
  

BFS

BFS(Breadth-First Search, 너비우선탐색)이란,
그래프 탐색을 할 때, 임의의 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.

• depth=1인 모든 노드를 방문한 후, depth=2인 모든 노드를 방문하고, 결국 depth=n인 노드 순으로 방문한다
• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다
• 그래프 탐색할 때 방문한 노드를 기록하고 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다 이를 무시하면 무한루프에 빠질 위험이 있다
• 방문한 노드들을 차례로 저장한 후 꺼내기 위해 자료구조 Queue를 사용한다FIFO
  

3. 코드

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

public class Main {

    static int[][] graph;
    static int[] visited;

    static void dfs(int cur, int num){
        visited[cur] = 1;
        System.out.print(cur + " ");
        //입력값을 그대로 사용하기 위해 1부터 시작
        for(int i = 1; i < num+1; i++){
            if(graph[cur][i] == 1 && visited[i] == 0){
                dfs(i, num);
            }
        }
    }

    static void bfs(int start, int num){
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start] = 1;
        System.out.print(start + " ");
        while(!q.isEmpty()){
            int cur = q.poll();
            for(int i = 1; i < num+1; i++){
                if(graph[cur][i] == 1 && visited[i] == 0){
                    visited[i] = 1;
                    q.offer(i);
                    System.out.print(i + " ");
                }
            }
        }
    }

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        StringTokenizer st = new StringTokenizer(input, " ");
        int vert = Integer.parseInt(st.nextToken());
        int edge = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());

        graph = new int[vert+1][vert+1];//좌표를 그대로 인수로 쓰기위해 +1
        //간선 연결 상태 기록
        for(int i = 0; i < edge; i++){
            String edge_list = br.readLine();
            StringTokenizer st2 = new StringTokenizer(edge_list, " ");
            int x = Integer.parseInt(st2.nextToken());
            int y = Integer.parseInt(st2.nextToken());
            graph[x][y] = graph[y][x] = 1;
        }
        visited = new int[vert+1];

        dfs(start, vert);
        System.out.println("");
        Arrays.fill(visited, 0);//초기화
        bfs(start, vert);
    }
}