[ 이론을 한 번에 ] BFS 이론 뿌수기

1. 개념적인 이론 부분

• 참고한 이론 강의 : https://inf.run/hpRtM

BFS (너비 우선 탐색) | Do it! 알고리즘 코딩테스트 with JAVA

 

1) BFS의 기본 이론

• BFS란?
  • 너비 우선 탐색. 즉, 그래프를 완전 탐색하는 방법 중 하나(DFS와 동일)
  • 시작 노드에서 출발해 시작 노드를 기준으로 가장 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘
  • FIFO(선입선출) 탐색.  Queue 자료 구조 사용!
  • 시간 복잡도(노드 수 :  V, 엣지 : E) : O(V + E)
  • 탐색 시 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장
  •  

BFS의 탐색 순서 ⭐⭐⭐⭐⭐

 

2) BFS의 핵심 동작 이론

1. BFS를 시작할 노드를 정한 후 사용할 자료구조를 초기화하기

• 방문했던 노드는 다시 방문하지 않는다.(visited 선언)
• 그래프를 인접 리스트로 표현(DFS와 동일)

 

     2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

 

     3. 큐 자료구조에 값이 없을 때까지 반복하기

 

기본적인 그림으로의 설명은 이해가 되기 쉬울 것이다. 그림의 저 순서대로 하면 되니까. 근데 여기서 한 가지 의문이 든다.

 

그러면 컴퓨터 상에서 저게 어떻게 저런 순서로 된다는거지? 라는 의문이 들었다.

 

이걸 알려면 그래프의 개념에 대해서도 알아야 하고, 특히 인접 행렬 방식을 이해하면 좋은데 여기서 설명하기 기니 관련하여 좋은 블로그를 하나 첨부하겠다! 그래프 관련 자료구조 내용은 C나 C++이 설명이 잘 되어 있는 것 같다.

 

https://suyeon96.tistory.com/32

[자료구조] 그래프 (Graph) - 인접행렬 vs 인접리스트, DFS, BFS, Connected Component, Spanning Tree

 

그래프에서 꼭 알고 있어야 하는 것이 간선과 엣지이다.

 

그래야 인접 행렬의 표 그리는 방식을 이해할 수 있다.

 

간선과 엣지로 표현해보면 연결하는 것에 따라 E가 위와 같이 표현된다.

 

 

간선과 엣지가 위와 같이 표현이 되니 아래와 같은 표가 나온다.

 

그런데 왜  E 순서가 아니라 양방향으로 되나요? 라는 질문이 나올 수 있다. 왜냐면 간단하게 표현해서 V(E)처럼 나타낸거지 실상은 연결을 위해 두 쪽 다 표현해줘야 하는 것이다!

그래프는 위와 같이 그려지고, 맨 오른쪽 표를 보면 최종적으로 visit하게 되는 그림인데 for문에 따라 먼저 있는 것들부터 돌면서 T 표시를 한다.

 

그렇기에 이 많은 내용을 생략하고 결론만 본다면

 

 

이 그림과 같은 그림으로 동작함을 알 수 있다!

 

이것만 이해한다면 왜 저렇게 굴러가는지 이해하기 쉬울 것이다!

 

근데 이론만으로는 실전 코드를 짜기는 어렵다! 실전 코드에서 핵심 내용을 외워보자!

 

2. 실전 코드

2-1. 의사코드로 먼저 코드 구조 떠올려 보기

 1) 미로 탐색하기

public class Main {
	dx, dy(상하좌우를 탐색하기 위한 define 값 정의 변수)
	A(데이터 저장 2차원 행렬)
	N(row), M(column)
	visited(방문 기록 저장 배열)

	public static void main(String[] args) {
		A 배열 초기화하기
		visited 배열 초기화하기
        
		// 데이터를 저장하는 부분
		for(N의 개수만큼 반복하기) {
			for(M의 개수만큼 반복하기) {
    				A 배열에 데이터 저장하기
    			}
		}

		BFS(0, 0) 실행하기
        	NOW 값 출력하기
	}
    
    public static void BFS(int i, int j) { // BFS 구현하기
	//큐 자료구조에 시작 노드 삽입하기(add 연산)
    	Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {i, j});
        
        visited[i][j] = true; // visited 배열에 현재 노드 방문 기록하기
        
        while(큐가 비어있을 때 까지){
		int now[] = queue.poll(); // 큐에서 노드 데이터를 가져오기(poll 연산)
        
		for(상하좌우 탐색){
			int x = now[0] + dx[k];
			int y = now[1] + dy[k];
            
                	if(유효한 좌표) {
                    	
                    	if(이동할 수 있는 칸이면서 방문하지 않은 노드) {
                     	   visited 배열에 방문 기록하기
                    	    A[x][y] = A[now[0]][now[1]] + 1; //A 배열에 depth를 현재 노드의 depth + 1로 업데이트하기
                    	    queue.add(new int[] {x, y}); // 큐에 데이터 삽입하기(add 연산)
                    }
                }
            }
        }
    }
}

 

 2) 나머지 유형..? 문제 푼 후 업데이트 해보겠습니다!

 

2-2. 문제에 적용해 보면서 BFS 풀어보기

https://www.acmicpc.net/step/24

https://school.programmers.co.kr/learn/courses/30/parts/12421

https://www.acmicpc.net/workbook/view/1983

https://www.acmicpc.net/workbook/view/9562

 

이걸 골드 5까지 최소 풀 수 있으면 코테에서 문제 없지 않을까?

 

3. 코테 때 외워 둘 기본 구조

• 이것도 문제를 푼 후 업데이트 할게요!

import java.util.*;