[백준] 1260 DFS와 BFS 자바

문제설명

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

 

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

 

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

 

✅ 통과한 코드 

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

public class Main {
    static boolean[] visited; //방문처리 배열
    static int[][] graph; //그래프의 연결상태

    static int n, m, v;

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

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

        graph = new int[n + 1][n + 1];
        visited = new boolean[n + 1];
        for (int j = 1; j <= n; j++) {
            Arrays.fill(graph[j], 0);
        }
        Arrays.fill(visited, false);

        for (int i = 1; i <= m; i++) {
            String edge = br.readLine();
            StringTokenizer st1 = new StringTokenizer(edge, " ");
            int a = Integer.parseInt(st1.nextToken());
            int b = Integer.parseInt(st1.nextToken());
            graph[a][b] = graph[b][a] = 1;
        }

        dfs(v);
        System.out.println();
        Arrays.fill(visited,false);
        bfs(v);
    }

    static void dfs(int node) {
        visited[node] = true; //방문시 true
        //방문노드 출력
        System.out.print(node+" ");

        //방문한 노드에서 인접한 노드 찾기
        for (int i = 1; i <= n; i++) {
            //인접한 노드가 방문한적 없다면 dfs 수행
            if (graph[node][i] == 1 && visited[i] == false) {
                dfs(i);
            }
        }
    }

    static void bfs(int node){
        Queue<Integer> queue=new LinkedList<>();
        queue.offer(node);
        visited[node]=true;

        while(!queue.isEmpty()){
            int tmp= queue.poll();
            //처음 방문 위치는 빼주기
            System.out.print(tmp+" ");

            for(int j=1; j<=n; j++){
                if(graph[tmp][j]==1 && visited[j]==false){
                    queue.offer(j);
                    visited[j]=true; // true 라면 방문
                }
            }
        }
    }
}