BFS / DFS 구분

BFS / DFS = 그래프 탐색 방법

 

DFS 

임의의 노드에서 다음 분기로 넘어가기전에 해당 분기를 완벽하게 탐색하는 방법

 

구현방법: Stack, 재귀함수

 

경로를 탐색할때, 한방향으로 갈 수있을때까지 계속 탐색

- > 더이상 갈 수 없다면, 다른 방향으로 다시 탐색 진행함

 

BFS

임의의 노드에 인접한 노드를 먼저 탐색하는 방법

가장 가까운 노드 먼저 방문 > > 멀리 떨어져있는 것은 나중에

 

- 구현방법 : Queue 사용

 

---

DFS VS BFS 문제 분류 방법

 

그래프의 모든 정점을 방문

-> DFS, BFS 사용

 

경로의 특징을 저장

-> DFS (BFS는 경로의 특징을 가질 수 없다)

-> DFS : 한경로상의 노드를 기억하기 때문에 적은 메모리를 사용한다.

 

최단 거리를 구해야할 때

-> BFS

(BFS는 너비를 우선으로 탐색하므로 현재 노드에서 가까운 곳부터 찾기때문에, 경로 탐색시 먼저 찾아지는 답이 곧 최단거리)

 

---

문제 ) 0과 1로 이루어진 그래프에서 0의 묶음을 찾는 문제

 

DFS

- 재귀 사용 종료조건, 시작조건 -> 반환값 true, false해서 체크

 

int[] dx = {0,0,-1,1};
int[] dy = {1,-1,0,0};

public void bfs(int x, int y) {
	if(x < 0 || x >= n || y < 0 || y >= m) {
    	return false;
    }
      
	map[x][y] = 1; // 방문처리
	for(int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(map[nx][ny] == 0) {
        	dfs(nx,ny);
        }
        return true;
    }
    return false;
}
public static void main(String[] args) {

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(dfs(i,j)) {
                answer++;
            }
        }
    }
}

 

 

BFS