[Baekjoon] 1260번 DFS와 BFS(feat. Java)

접근

• DFS 는 재귀호출
• BFS 는 Queue 가 핵심
• 접점이 이어진 간선을 어떻게 구성할것이냐가 핵심
  • 이중 배열을 통해 접점간에 간선을 표시
  • 인덱스 접근의 편의를 위해 0번째 자리는 패딩설정

 

---

 

해결

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

public class Main {

    public static String dfs = "";
    public static int[][] arr1;
    public static int[][] visited1;
    public static List<Integer> visitedElement1;

    public static String bfs = "";
    public static int[][] arr2;
    public static int[][] visited2;
    public static List<Integer> visitedElement2;

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

        int N = Integer.parseInt(st1.nextToken());
        int M = Integer.parseInt(st1.nextToken());
        int V = Integer.parseInt(st1.nextToken());

        arr1 = new int[N+1][N+1];
        visited1 = new int[N+1][N+1];
        visitedElement1 = new ArrayList<>();

        arr2 = new int[N+1][N+1];
        visited2 = new int[N+1][N+1];
        visitedElement2 = new ArrayList<>();

        for(int i=0;i<M;i++){
            StringTokenizer st2 = new StringTokenizer(br.readLine());

            int A = Integer.parseInt(st2.nextToken());
            int B = Integer.parseInt(st2.nextToken());

            arr1[A][B] = 1;
            arr1[B][A] = 1;
            arr2[A][B] = 1;
            arr2[B][A] = 1;
        }

        dfs(N, V);
        bfs(V);

        System.out.println(dfs.trim());
        System.out.print(bfs.trim());
    }

    public static void dfs(int N, int V){

        dfs += V+" ";

        visitedElement1.add(V);

        int[] arr = arr1[V];
        int[] visited = visited1[V];

        for(int i=1;i<=N;i++){
            if(i == V)
                continue;

            if(arr[i] == 1 && visited[i] == 0 && !visitedElement1.contains(i)){
                visited1[V][i] = 1;
                visited1[i][V] = 1;
                dfs(N, i);
            }
        }
    }

    public static void bfs(int V) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(V);
        visitedElement2.add(V);

        while(!queue.isEmpty()){
            int v = queue.poll();
            bfs += v+" ";

            for(int i=1;i<arr2[v].length;i++){
                if(arr2[v][i] == 1 && visited2[v][i] == 0 && !visitedElement2.contains(i)){
                    queue.add(i);
                    visited2[v][i] = 1;
                    visited2[i][v] = 1;
                    visitedElement2.add(i);
                }
            }
        }
    }
}