[ ALGO ] BJ1260_DFS-AND-BFS ( 깊이우선탐색, 넓이우선탐색 )

4 min readJan 10, 2017

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

main함수에서는 입력을 받고, matrix를 1로 초기화하고, DFS와 BFS는 main함수 외부에 구현하였습니다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;public class Main {public static void main(String[] args) {
  // TODO Auto-generated method stub
/*
4 5 1
1 2
1 3
1 4
2 4
3 41 2 4 3
1 2 3 4
*/    
  
  //입력부 
  Scanner sc = new Scanner(System.in);
  int v = sc.nextInt(); 
  int e = sc.nextInt(); 
  int s = sc.nextInt();  
    //matrix를 1로 초기화 
  int matrix[][] = new int[v+1][v+1];
  for( int i=1; i<=e; i++)
  {
   int x = sc.nextInt(); int y = sc.nextInt();
   matrix[x][y]=1;
   matrix[y][x]=1;
  }
    //DFS AND BFS
  int check[] = new int[matrix[0].length];  
  DFS(matrix, check, s);
  System.out.println("");
  check = new int[matrix[0].length];
  BFS(matrix, check, s);
 }

DFS는 depth first search의 약자로 깊이 우선 탐색을 뜻합니다. 반복적 혹은 재귀적인 방식으로 구현을 할 수 있습니다. 저는 재귀적인 방식을 이용하여 구현하였습니다.

특정 노드로 가는 길이 있고(조건1 : m[p][i]==1) 그 노드가 방문하지 않은 노드라면 (조건2 : check[i]==0) 그 노드로 이동하여 다시 DFS를 수행합니다. check 배열은 방문 여부를 표기하는 배열로 방문할 때마다 방문 노드의 인덱스에 해당하는 check배열에 1을 대입합니다.

public static void DFS( int m[][],int check[], int p){  
  
  System.out.print(p+" ");
  check[p]=1;
  
  for( int i=1; i<m[0].length; i++ )
  {
   if(m[p][i]==1 && check[i]==0){
    DFS(m, check, i);
   }
  }
}

BFS는 breadth first search의 약자로 너비우선탐색을 뜻합니다. 큐를 이용하여 구현할 수 있습니다. 우선 큐에 시작 노드를 추가합니다. 그리고 큐가 비어있지 않다면 poll() 함수로 front에 있는 요소가 가리키는 노드로 이동합니다. 그리고 그 특정 노드로 이동한 후 현재 노드와 직접 연결된 노드들의 인덱스를 큐에 추가합니다.

다시 큐에서 front를 뽑아내어 해당 노드로 이동하고 직접 연결된 노드들의 인덱스를 큐에 추가하는 방식을 반복합니다. 큐가 empty 상태가 될 때까지 이러한 과정을 반복합니다.

 public static void BFS( int m[][],int check[], int p){  
  
  Queue<Integer> q = new LinkedList<Integer>(); 
  
  check[p]=1;
  q.add(p);
  
  while(!q.isEmpty())
  {
   int node = q.poll();
   System.out.print(node+" ");
   for( int i=0; i<m[0].length; i++)
   {
    if(m[node][i]==1 && check[i]==0){
     check[i]=1;
     q.add(i);
    }
   }   
  }  
 }
}

아래 전체 소스 코드를 첨부합니다.

[ ALGO ] BJ1260_DFS-AND-BFS ( 깊이우선탐색, 넓이우선탐색 )

Written by peter_yun