[백준/JAVA] 1260번

DFS와 BFS

1260번으로 이동

DFS와 BFS를 구하기 위해

• DFS: 깊이 우선 탐색 / BFS: 너비 우선 탐색
• 그래프를 표현하기 위해서 인접행렬 graph[][] 사용
• 방문한 노드인지 확인하기 위해 check[] 사용
• 재귀함수를 사용해 DFS 구현
• 큐를 사용해 BFS 구현

코드 리뷰

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

public class Main {
  public static int N,M,V;
  public static int[][] graph;
  public static boolean[] check;

  public static void main(String[] args) throws Exception {
    
  Scanner sc = new Scanner(System.in);

  N = sc.nextInt();
  M = sc.nextInt();
  V = sc.nextInt();

  graph = new int[N+1][N+1];
  check = new boolean[N+1];
  
  for(int i=0; i<M; i++){
    int x = sc.nextInt();
    int y = sc.nextInt();

    // 입력받은 간선들의 위치는 1로 fix해줌 
    graph[x][y] = 1;
    graph[y][x] = 1;
  }

  dfs(V);
  System.out.println();
  Arrays.fill(check,false);
  bfs(V);
  }

  public static void dfs(int start){
    //시작점은 방문되었으니 true로 변환
    check[start] = true;
    System.out.print(start + " ");

    for(int i=1; i<N+1; i++){
      // 만약에 시작점과 연결된 곳이 1이고, check[i]가 false이면 아직 방문하지 않은 노드이므로 
      // dfs(i)로 불러주면, 그것과 연결된 점이 시작점이 되므로 dfs를 구현가능
      
      if(graph[start][i]==1 && !check[i])
        dfs(i);
    }
  }

  public static void bfs(int start){
    Queue<Integer> q = new LinkedList<>();
    q.offer(start);
    check[start] = true;

    while(!q.isEmpty()){
      int vertex = q.poll();
      System.out.print(vertex + " ");

      for(int i=1; i<N+1; i++){
        // 시작점과 연결된 노드가 1이고 Check[i]가 false이면, for문을 통해서 시작점과 연결된 모든 점들을 
        // 큐에 담고 check[i]는 True로 바꿔준다.
       
        if(graph[vertex][i]==1 && !check[i]){
          q.offer(i);
          check[i] = true;
        }

      }

    } 

  }
}

---

참고한 URL

https://leveloper.tistory.com/35