[백준/Java] 1260 DFS와 BFS

알 수 없는 사용자 2023. 8. 20. 17:13

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

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net

DFS와 BFS의 기본 구현문제입니다.

기본적으로는 dfs는 스택, bfs는 큐를 통해 구현하였습니다.

그리고 탐색 문제는 방문 여부를 판단하는 boolean 배열이 필요하므로, isVisit배열을 만들어 문제를 해결합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    static int N;
    static int M;
    static int k;
    static ArrayList<Integer> arr[];
    static boolean[] isVisit;
    static StringBuilder sb;
    public static void main(String[] args) throws NumberFormatException, 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());
        k=Integer.parseInt(st.nextToken());

        arr= new ArrayList[N+1]; //좌표를 그대로 받아들이기 위해 +1 사용
        isVisit=new boolean[N+1];
        sb= new StringBuilder();
        for(int i=0;i<arr.length;i++){
            arr[i]=new ArrayList<>();
        }

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

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

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

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

    }
    public static void dfs(int index){
        isVisit[index]=true;
        sb.append(index+" ");
        for(int i:arr[index]){
            if(!isVisit[i])
                dfs(i);
        }
    }
    public static void bfs(int index){
        isVisit[index]=true;
        Queue<Integer> q= new LinkedList<>();
        q.add(index);
        while (!q.isEmpty()){
            int a= q.poll();
            sb.append(a+" ");
            for(int i: arr[a]){
                if(!isVisit[i])
                {
                    q.add(i);
                    isVisit[i]=true;
                }
            }
        }
    }
}

저작자표시 (새창열림)