[백준] DFS와 BFS - 1260번

문제설명

 

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

기본아이디어

DFS와 BFS 구현 문제이다. 어렵지 않은 문제이지만, DFS와 BFS를 잘 모르는 사람에게는 필요할 거 같아서 올려놓았다. 특히 DFS는 완전탐색, 깊이 우선 탐색으로 많이 알고 있지만 BFS, 넓이 우선 탐색은 생소한 사람들은 코드를 보면 쉽게 알 수 있을 것이다. BFS 코드에 관해서는 DFS와 달리 재귀로 풀지 않고 탐색해야하는 곳을 Queue에 저장하고 Queue에 저장된 순서대로 진행을 하기 때문에 넓이 우선, 즉 트리를 예로 들자면 한 depth씩 탐색을 하게 된다. 여기서 응용을 하게 되면 PriorityQueue를 적용해서 최단거리를 구할 수 도 있다. 넓이 우선 탐색을 하면서 거리를 PriorityQueue에 저장하면서 진행하면 제일 앞에 있는 값이 최단거리를 유지할 수 있으므로 도착점에 제일 먼저 도착한 값 하나가 정답이 된다.

성공!

 

구현코드

public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));
 
        StringTokenizer str = new StringTokenizer(input.readLine());
        int N = Integer.parseInt(str.nextToken());
        int M = Integer.parseInt(str.nextToken());
        int V = Integer.parseInt(str.nextToken());
 
        graph = new ArrayList[N+1];
        for(int i = 0; i<=N; i++)
            graph[i] = new ArrayList<>();
 
        for(int i = 0; i < M; i++){
            str = new StringTokenizer(input.readLine());
            int a = Integer.parseInt(str.nextToken());
            int b = Integer.parseInt(str.nextToken());
            graph[a].add(b);
            graph[b].add(a);
        }
 
        for(int i = 0; i <= N; i++){
            Collections.sort(graph[i]);
        }
 
        visited = new boolean[N+1];
        visited[V] = true;
        output.append(V + " ");
        dfs(V);
        output.append("\n");
 
        visited = new boolean[N+1];
        visited[V] = true;
        output.append(V + " ");
        bfs(V);
 
        System.out.println(output);
    }
    static int N, M, V;
    static boolean[] visited;
    static List<Integer>[] graph;
 
    static void dfs(int idx){
        for(int i = 0; i < graph[idx].size(); i++){
            int temp = graph[idx].get(i);
            if(visited[temp])
                continue;
 
            visited[temp] = true;
            output.append(temp + " ");
            dfs(temp);
        }
    }
    static void bfs(int idx){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(idx);
        while(!queue.isEmpty()) {
            int now = queue.poll();
            for (int i = 0; i < graph[now].size(); i++) {
                int temp = graph[now].get(i);
                if (visited[temp])
                    continue;
 
                visited[temp] = true;
                output.append(temp + " ");
                queue.add(temp);
            }
        }
    }

 

 

 

정리, 기억할 내용

1. DFS 와 BFS 구분, 잘 적용

2. BFS 구현 방법 -> 큐 자료구조 사용, Priority Queue도 기억