[JAVA] 백준 1260번 - DFS와 BFS

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

1260번: DFS와 BFS

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
    static int n, m, v;
    static int[][] arr;
    static boolean[] visit;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st= new StringTokenizer(br.readLine());

         n = Integer.parseInt(st.nextToken());
         m = Integer.parseInt(st.nextToken());
         v = Integer.parseInt(st.nextToken());

        arr = new int[n+1][n+1];
        visit = new boolean[n+1];

        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][b] = arr[b][a] = 1;
        }

        dfs(v);
        sb.append("\n");
        visit = new boolean[n+1];

        bfs(v);
        System.out.println(sb);
    }
    public static void dfs(int v){
        if(visit[v]) return;
        visit[v] = true;

        sb.append(v+" ");

        for(int i=1; i<=n; i++){
            if(arr[v][i] == 1 && !visit[i]){ // 간선이 있고 방문하지 않았던 노드라면
                dfs(i);
            }
        }
    }

    public static void bfs(int v){
        Queue<Integer> q = new LinkedList<>();
        visit[v] = true;
        q.offer(v); // 큐에 노드 삽입

        while(!q.isEmpty()){
            v = q.poll(); // 처음 삽입한 노드
            sb.append(v+" ");

            for(int i=1; i<=n; i++){
                if(arr[v][i] == 1 && !visit[i]){ // 인접한 노드이고 방문하지 않았다면
                    q.offer(i); // 큐에 삽입
                    visit[i] = true; // 방문 체크
                }
            }
        }
    }
}

 

 

 

bfs와 dfs 기본 문제!