BFS 란 Breadth-first search(너비우선탐색) 이다.
- 인접한 노드들을 먼저 탐색 한다는 뜻이다.
자식을 먼저 탐색.
문제를 풀면서 느낀점은 대부분의 BFS로 풀 수 있는문제들은 DFS로도 풀수있다. - 결론적으로 bfs는 미로문제,영역문제 등을 풀때 사용하고 백트레킹 문제를 풀때 DFS를 사용하는 것이 좋겠다라고 생각하게 되었다.
- 개념
그래프 탐색: 어떤것들이 연속해서 이어질때, 모두 확인하는방법
Graph: Vertex(어떤것) + Edge(이어지는것)
시간복잡도: O(V+E)
이차원 배열에서 v = 배열의 개수
E = 4V
5V
문제를 풀때는 어떻게 풀까?
프로그래머스에서 풀어보았던 카카오 프렌즈 컬러링북 문제를 예로들어서 설명해보겠습니다.
문제 풀이링크: https://velog.io/@cse05091/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Level2-3%EC%B9%B4%EC%B9%B4%EC%98%A4-%ED%94%84%EB%A0%8C%EC%A6%88-%EC%BB%AC%EB%9F%AC%EB%A7%81%EB%B6%81
문제를 풀기 위해선 모든 배열을 모두 확인해야하고 상,하,좌,우 를 확인하며 같은 색인지 판단 후 총 영영의 수,가장 큰 영역의 넓이를 구하는 문제입니다.
BFS 알고리즘에 대해서 잘 이해하고 있는 사람들은 실수를 안하겠지만 대충이해하고 푸는 사람들이 가장많이 실수하는 부분이 방문여부를 체크하지 않는 것입니다.
이차원배열로 값이 주어졌기 때문에 우리는 그 이차원배열을 모두 확인해야합니다. 그렇기 때문에 이중 for문으로 검사를 해줍니다.
for(int i = 0; i < m; i++){
for(int j = 0;j <n ; j++){
if(visited[i][j] != true && picture[i][j] != 0 ){
size = 1;
bfs(i, j, m, n, picture);
if(maxSizeOfOneArea < size) maxSizeOfOneArea = size;
numberOfArea++;
}
}
}방문여부가 true가 아니면서, 배열 값이 0 이 아닐때 총 size = 1로 초기화 시켜주고 bfs메서드를 실행시킵니다.
bfs 메서드는 다음과 같습니다.
public void bfs(int x, int y, int m, int n, int[][] picture){
queue.add(new Node(x,y));
visited[x][y] = true;
while(!queue.isEmpty()){
Node now = queue.poll();
for(int i = 0; i < 4; i++){
int kx = now.x + dx[i];
int ky = now.y + dy[i];
if(0 <= kx && kx < m && 0 <= ky && ky < n){
if(visited[kx][ky] != true && picture[x][y] == picture[kx][ky]){
queue.add(new Node(kx,ky));
visited[kx][ky] = true;
size++;
}
}
}
}
}처음 값을 queue에 넣어줍니다. 그 후 방문여부를 true 로 바꿔주고
queue가 empty 일때 까지 반복해줍니다.
처음 값을 pool 해서 상, 하, 좌, 우 의 좌표값이 영역에 맞는지 확인한 후 맞다면 방문했는지,0이아닌지 확인 후 queue에 더해주는 것입니다. 이때 size 는 더해줍니다.
저도 착각을 많이했고 많은 분들이 착각을 많이 하는 부분이 bfs는 자식을 먼저 본다고 했는데 무엇이 자식인가? 이문제에선 상하좌우 에 인접한 배열이 자식이라고 생각하시면 됩니다.
