[알고리즘] BFS (너비 우선 탐색)

BFS 개념

BFS : 너비 우선 탐색

<-> DFS : 깊이 우선 탐색

 

그래프를 탐색하는 기법 

 

BFS 구현을 위해서는 Queue를 사용

 

 

---

 

 

BFS는 너비 우선 탐색 기법으로 깊이 우선 탐색인 DFS와 상반되는 개념입니다.

 

DFS와 BFS는 모두 그래프를 탐색하는 기법입니다.

 

 

가령 위와 같은 트리가 존재한다면, BFS는 위에 위치한 노드부터 순차적(Level)으로 탐색을 진행합니다.

 

BFS : 2 -> 7 -> 5 -> 2 -> 6 -> 9 -> 5 -> 11 -> 4

DFS : 2 -> 7 -> 2 -> 6 -> 5 -> 11 -> 5 -> 9 -> 4

 

너비 탐색을 수행은 위에 작성된 것 처럼 상위 Level에 위치한 노드 (Lv 0 : 0 | Lv 1 : 7, 5 | ...)들이 먼저 탐색되는 것을 볼 수 있습니다.

 

 

이러한 로직은 Queue 자료구조를 통해서 쉽게 구현이 가능합니다.

 

자료구조에 데이터를 저장하는 순서는 데이터를 Queue에서 제거하면서 제거된 데이터의 자식을 Queue에 삽입하는 방식으로 이루어집니다.

 

가령 Lv0인 2가 Queue에 먼저 저장되어 있는 상태에서 2를 제거하게 된다면 2의 자식인 7과 5를 Queue에 삽입합니다.

 

다음 Queue에 저장된 순서대로 7을 제거한다면 7의 자식인 2와 6이 Queue에 삽입될 것이고,

이후 5를 제거하면 9가 들어오게 될 것입니다.

 

 

 

 

사용처

지도 문제 해결에 사용

지도 문제 == 2차원 배열 == 그래프 탐색 

 

대표적인 알고리즘 문제

1) 최단 거리 찾기 (level)

2) 섬(덩어리) 찾기

3) 감염 (level)

 

 

---

 

BFS는 앞서 언급하였듯이 그래프를 탐색하는데 사용하는 알고리즘입니다.

 

대표적으로 지도 문제가 그래프를 탐색하는 대표 문제인데요.

 

지도는 일반적으로 2차원 배열로 표현할 수 있으며, 2차원 배열 탐색은 그래프와 유사하기 때문입니다.

 

특히 지도 문제 중에서도 최단 거리 찾기, 섬 개수 찾기 등의 문제를 푸는데 사용할 수 있습니다.

 

 

 

기본 로직

Queue에 들어갈 객체 생성 (Point)
Queue 생성

Queue에 시작점 객체 삽입

Queue에 아무것도 없을 때까지 반복
    Queue의 객체 꺼냄
    문제 조건 & 지도 범위에 따라 탐색
        조건에 맞는 경우 Queue에 삽입

전반적인 로직은 위와 같은 형태로 진행됩니다.

 

Queue는 탐색을 위한 노드들을 저장하기 위해서 사용됩니다.

 

Queue에 저장 될 데이터는 위치를 찾아야 하므로 (X, Y)좌표를 필요로 합니다.

만약 최단 거리 등 거리나 시간을 구해야 하는 경우에는 추가적으로 level 정보를 저장해야 합니다.

따라서 Queue에 들어갈 데이터는 일반적으로 객체 또는 배열을 저장하게 됩니다.

 

Queue를 생성한 후에는 시작점 객체를 삽입하고, Queue가 아무것도 없을 때까지 반복합니다.

 

반복을 하다가 제시한 조건에 맞는 요소를 찾게 된다면 Queue에 추가적으로 데이터를 삽입합니다.

 

 

 

구현

// 조건이 맞는지 확인하기 위한 4방/8방 탐색
static int[] dr = {1, -1, 0, 0};
static int[] dc = {0, 0, 1, -1};

// 지도 정보 저장 2차원 배열
static int [][] map;


// Queue에 저장될 노드 객체
static class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}


// 노드 저장할 Queue 
Queue<Point> q = new LinkedList<>();

// Queue가 빌 때까지 반복
while (!q.isEmpty()) {
	Point p = q.poll();
	map[p.r][p.c] = 0;
	for (int i = 0; i < 4; i++) {
		int nr = p.r + dr[i];
		int nc = p.c + dc[i];
		if (nr >= 0 && nr < N && nc >= 0 && nc < M // 지도 안에 있다면
				&& v[nr][nc] == false && map[nr][nc] == 1) { 
			v[nr][nc] = true; // 방문 체크
			q.add(new Point(nr, nc));
		}
	}
}

 

전체적인 구현 코드는 아래 대표 문제 풀이를 통해서 확인할 수 있습니다.

 

아래에 단지번호 붙이기를 참고해주세요.

 

 

 

대표 문제

- 백준 2667 단지번호붙이기
https://www.acmicpc.net/problem/2667

https://angelplayer.tistory.com/405

 

- 백준 1012 유기농배추
https://www.acmicpc.net/problem/1012

https://angelplayer.tistory.com/406

 

- 백준 4963 섬의갯수
https://www.acmicpc.net/problem/4963

https://angelplayer.tistory.com/407

 

- 백준 7576 토마토
https://www.acmicpc.net/problem/7576

https://angelplayer.tistory.com/408

 

- SWEA 7733 치즈 도둑 

https://angelplayer.tistory.com/409

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWrDOdQqRCUDFARG&categoryId=AWrDOdQqRCUDFARG&categoryType=CODE&&&