BFS란

• 너비 우선 탐색(Breadth First Search, BFS) 이다.

• 탐색 시작점(임의의 시작점)의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식

• 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용함

static public void bfs(){
	Queue.add(0,0) //탐색 시작점
    visited[0][0] = true;
    
    while(!Queue.isEmpty()){
    	cur=Queue.poll();
        for(cur과 연결된 것들) //보통 사방 탐색으로 1~4를 진행
        	if(방문 여부, 조건)
            	visited[i][j] = true;
                Queue.add(nr,nc);
    }
}

DFS란

• 우선 탐색(Depth First Search, DFS)으로,
  시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법

• 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 재귀적으로 구현하거나 후입선출 구조의 스택 사용

static public void dfs(r,c){//정점
	visited[r][c] = true;
    for (정점과 연결된 것들)
    	if(방문 여부, 조건)
        	vistied[nr][nc] = true;
            dfs(nr,nc);
}