백준 1260_DFS와 BFS_JAVA

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

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

public class Main {
    static int N,M,V;
    static boolean[] visitedDFS;
    static boolean[] visitedBFS;
    static ArrayList<Integer>[] grid;
    static StringBuilder sb;

    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()); // 탐색 시작 정점
        visitedDFS = new boolean[N+1];
        visitedBFS = new boolean[N+1];
        grid = new ArrayList[N+1];

        // 2차원 배열로 생성
        for (int i=1; i<N+1; i++) {
            grid[i] = new ArrayList<>();
        }

        for(int i=1; i<M+1; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            grid[s].add(e); // 정점간 방향이 없기 때문에
            grid[e].add(s); // 둘다 추가
        }

        // 정점 번호가 작은 것을 먼저 방문
        for (int i=1; i<N+1; i++){
            Collections.sort(grid[i]);
        }

        sb = new StringBuilder();

        DFS(V);
        sb.append("\n");
        BFS(V);

        System.out.println(sb);
    }

    private static void DFS(int v) {
        visitedDFS[v] = true;
        sb.append(v + " ");

        for(int i:grid[v]) {
            if(!visitedDFS[i]) {
                DFS(i);
            }
        }
    }

    private static void BFS(int v) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(v);
        visitedBFS[v] = true;

        while(!queue.isEmpty()) {
            int cur = queue.poll();
            sb.append(cur + " ");
            for(int i:grid[cur]) {
                if(!visitedBFS[i]) {
                    queue.add(i);
                    visitedBFS[i] = true;
                }
            }


        }
    }

}

 

 

회고

- 기본적인 BFS, DFS 구현 문제였다.

- 생각보다 헷갈리고 오래걸렸다.

- BFS와 DFS에 더 적응 할 수 있도록 연습을 해야겠다.