끄적끄적 코딩
article thumbnail
Published 2023. 1. 23. 22:30
[Java] 백준 1260번 DFS와 BFS 알고리즘

DFS와 BFS를 구현하는 문제입니다.

재귀함수를 통해서 DFS를 구현하고
Queue를 활용해서 BFS를 구현해 주었습니다.

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

public class Main {
  public static int n;
  public static int m;
  public static int v;
  public static boolean [][] arr;
  public static boolean[] visit;
  public static void main(String args[]) throws Exception{
	  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int a, b;
    int num;
    Queue<Integer> queue = new LinkedList<>();
    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());
    v = Integer.parseInt(st.nextToken());
    visit = new boolean[n+1];
    arr = new boolean[n+1][n+1];

    for(int i=0; i<m; ++i){
      st = new StringTokenizer(br.readLine());
      a = Integer.parseInt(st.nextToken());
      b = Integer.parseInt(st.nextToken());
      
      arr[a][b] = true;
      arr[b][a] = true;
    }

    visit[v] = true;
    DFS(v);
    System.out.printf("%n");
    
    Arrays.fill(visit, false);
    visit[v] = true;
    queue.add(v);
    while(queue.size() != 0){
      num = queue.poll();
      System.out.printf("%d ", num);

      for(int i=0; i<n+1; ++i){
        if(arr[num][i] & !visit[i]){
          visit[i] = true;
          queue.add(i);
        }
      }
    }
  }

  public static void DFS(int num){
    System.out.printf("%d ", num);
    for(int i=0; i<n+1; ++i){
      if(arr[num][i] && !visit[i]){
        visit[i] = true;
        DFS(i);
      }
    }
  }
}

'알고리즘' 카테고리의 다른 글

[Java] 백준 15650번 N과 M (2)  (0) 2023.01.23
[Java] 백준 15649번 N과 M (1)  (0) 2023.01.23
[Java] 백준 10845번 큐  (0) 2023.01.23
[Java] 백준 14891번 톱니바퀴  (1) 2023.01.20
[Java] 백준 14889번 스타트와 링크  (0) 2023.01.19

검색 태그