DFS와 BFS - 1260번

 

---

풀이 방법

전형적인 bfs, dfs 문제로 풀어보면 둘의 차이점을 잘 알 수 있다.

방문할 수 있는 정저미 여러개인 경우 정점 번호가 작은것을 먼저 방문한다는 조건으로 정렬한번만 해주면 되는 문제 였다.

 

내 코드

package com.company;

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

public class Main {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static Boolean[] visited;
    static int N, M, V;

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

        for (int i = 0; i < graph.get(V).size(); i++) {
            int x = graph.get(V).get(i);
            if (!visited[x]) {
                dfs(x);
            }
        }
    }

    static void bfs(int V) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(V);
        visited[V] = true;


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

            for (int i = 0; i < graph.get(y).size(); i++) {
                int x = graph.get(y).get(i);
                if (!visited[x]) {
                    q.offer(x);
                    visited[x] = 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());

        visited = new Boolean[N + 1];
        Arrays.fill(visited, false);

        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            graph.get(a).add(b);
            graph.get(b).add(a);
        }
        for (int i = 0; i <= N; i++) {
            Collections.sort(graph.get(i));
        }
        dfs(V);

        System.out.println();
        Arrays.fill(visited, false);

        bfs(V);
        System.out.println();

    }
}