[알고리즘] 백준 1260 DFS와 BFS

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

 

public class BOJ_1260 {
    static int n, m, v;
    static int[][] map;
    static boolean[] visited;

    public static void dfs(int s) {
        System.out.print(s + " ");
        visited[s] = true;

        for (int i = 1; i < n + 1; i++) {
            if (map[s][i] == 1 && !visited[i])
                dfs(i);
        }
    }

    public static void bfs(int s) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(s);
        visited[s] = true;

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

            for (int i = 1; i < n + 1; i++) {
                if (map[k][i] == 1 && !visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        StringTokenizer st = new StringTokenizer(s, " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        v = Integer.parseInt(st.nextToken());
        map = new int[n + 1][n + 1];
        visited = new boolean[n + 1];

        for (int i = 0; i < n + 1; i++) {
            Arrays.fill(map[i], 0);
        }

        for (int i = 0; i < m; i++) {
            String str = br.readLine();
            StringTokenizer st2 = new StringTokenizer(str, " ");
            int a = Integer.parseInt(st2.nextToken());
            int b = Integer.parseInt(st2.nextToken());
            map[a][b] = 1;
            map[b][a] = 1;
        }

        dfs(v);
        System.out.println();
        Arrays.fill(visited, false);
        bfs(v);
    }
}

아주 기초적인 DFS, BFS 문제이다.

 

DFS는 일단 시작하는 정점을 방문하여 visited[s]를 true값으로 바꿔주었다.

 

그 후 반복문을 통해 정점끼리 이어져있으며 방문하지 않은 정점이 나왔을 경우에 재귀를 타도록 하였다.

 

BFS의 경우에는 먼저 방문하지 않은 정점을 큐에 넣은다음 visited값을 true로 바꿔준다. 

 

그 후 큐가 빌때까지 큐에서 정점들을 하나씩 빼며 그 정점과 인접하고있는 정점을 탐색하면서 위 내용을 반복하면 된다.

 

코드가 이해가지 않는 경우에는 DFS와 BFS의 이론 공부가 필요하다.