[백준/자바] DFS와BFS - Java 1260

import java.util.*;
 
public class dfs와bfs {
 
    static int n,m,v,s,e;
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 노드 개수
        m = sc.nextInt(); // 간선 개수
        v = sc.nextInt(); // 시작점
        A = new ArrayList[n+1];
 
        for (int i=1; i<=n; i++){ // 그래프 정보 개수
            A[i] = new ArrayList<Integer>();
        }
 
        for (int i=1; i<=m; i++){
            s = sc.nextInt(); // 노드간의 시작점
            e = sc.nextInt(); // 노드간의 끝점
            A[s].add(e); // 시작점-끝점 이어주기
            A[e].add(s); // 끝점-시작점 이어주기
            /*System.out.println("A["+s+"] : " + A[s]);
            System.out.println("A["+e+"] : " + A[e]);*/
        }
 
        for (int i=1; i<=n; i++){
            Collections.sort(A[i]);
        } // 정점 번호가 작은 것을 먼저 방문
 
        visited = new boolean[n+1]; // 노드를 visited[1]부터 넣기 위해 n+1로 선언
        dfs(v);
        System.out.println();
 
        visited = new boolean[n+1];
        bfs(v);
        System.out.println();
 
 
 
        }
 
        public static void dfs(int node){
            System.out.print(node +" ");
            visited[node] = true; // 방문
            for (int i : A[node]){ // A 배열에 담긴 개수만큼 반복
                if(!visited[i]){ // A 배열에 담긴 숫자중에 방문하지 않은 게 있다면
                    dfs(i);
                }
            }
        }
 
        public static void bfs(int node){
            Queue<Integer> q = new LinkedList<>(); // 큐 생성
            q.add(node); // 큐에 노드를 넣어준다
            visited[node] = true; // 방문
 
            while(!q.isEmpty()){ // 큐가 비어있을때까지 반복
                int now_node = q.poll(); // 맨 앞 큐 값을 밀어내기
                System.out.print(now_node + " "); // 그거 출력
                for (int i:A[now_node]){
                    if(!visited[i]){
                        visited[i] = true;
                        q.add(i);
                    }
                }
            }
        }
}
 

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

1260번: DFS와 BFS

 

실버 문제이지만 dfs, bfs에 대한 개념이 없어서 많은 애를 먹은 문제였다.

포기하지 말고 꾸준히 공부하자! dfs, bfs 문제는 비슷한 유형이 많아서 한 번 감을 잡으면 다른 문제는 풀기 쉽다고 한다.

나 자신도 이걸 보는 모두도 포기하지 말고 끝까지 하자