[백준] 1260번 DFS와 BFS

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

1260번: DFS와 BFS

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

public class Main {

    // 정점 개수
    static int N;
    // 간선 개수
    static int M;
    static ArrayList<Integer>[] list;
    static boolean[] visit;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        // 탐색 시작
        int V = sc.nextInt();

        list = new ArrayList[N + 1];
        visit = new boolean[N + 1];
        for(int i = 0; i < list.length; i++) {
        	list[i] = new ArrayList<>();
        }

        // 간선연결상태 저장
        for(int i = 0; i < M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            list[a].add(b);
            list[b].add(a);
        }

        for(int i = 0; i < list.length; i++) {
        	Collections.sort(list[i]);
        }

        dfs(V);
        sb.append("\n");
        visit = new boolean[N + 1];
        bfs(V);
        System.out.println(sb);
    }

    public static void dfs(int index) {
        visit[index] = true;
        // 현재 노드에 해당하는 리스트 모두 하나씩 할당
        sb.append(index).append(" ");
        for(int i : list[index]) {
            if(!visit[i]) {
                //  할당한 값을 노드로 바꾸어 재귀호출
                dfs(i);
            }
        }
    }

    public static void bfs(int index) {
        visit[index] = true;
        Queue<Integer> queue = new LinkedList<>();
        // 1. 탐색 시작 노드를 큐에 넣고 방문처리
        queue.add(index);
        while(!queue.isEmpty()) {
            // 2.큐에서 노드를 꺼냄
            int a = queue.poll();
            sb.append(a).append(" ");
            // 3. 해당 노드의 리스트 중 방문하지 않은 노드를 큐에 넣고 방문처리
            for(int i : list[a]) {
                if(!visit[i]) {
                    queue.add(i);
                    visit[i] = true;
                }
            }
		}
	}

}

 

 

2021.03.09 - [Algorithm/이론] - 탐색 알고리즘 DFS / BFS

탐색 알고리즘 DFS / BFS