[알고리즘] BFS

변수 설명

board = 판

vis = 방문 여부

n,m 각각 행과 열의 개수

dx,dy = 상하좌우 처리 위한 변수

 

1. (0,0) 방문 처리 후 큐에 추가

2. 상하좌우 살피며 큐에 추가

3. 큐의 front를 cur에 저장 후 pop

4. dx,dy를  활용하여 상하좌우 탐색

(대부분 x가 행 , y 가 열을 의미함)

5. dx,dy 가 범위에 있는지 부터 확인 중요(처리 안 할 시에 런타임 에러남)

 

자주 하는 실수

1. 시작점에 방문했다는 표시를 남기지 않음

2. 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 방문했다는 표시를 남김 -> 시간초과 혹은 메모리 초과 발생

3. 이웃한 원소가 범위를 벗어났는지에 대한 체크를 잘못 함

 

bfs 문제

기본

1926: 그림

1. 상하좌우로 연결된 그림의 크기를 알아내기

2. 도화지에 있는 모든 그림을 찾아내기 => 이중 for문을 사용하여 시작 위치 찾기

3. 각 칸이 queue에 한번씩만 들어가므로 시간 복잡도는 o(nm) 

 

응용1 - 거리측정

2178: 미로 탐색

최단 경로의 길이 찾기 문제. bfs를 이용해 모든 경로의 최단 경로를 찾을 수 있음

시작점에서 현재 위치까지의 거리를 현재 원소 위치에 저장

초기화를 -1로 하면 vis 배열을 두지 않아도 됨

 

 

응용2 - 시작점 여러개

7578: 토마토

일반 bfs 문제처럼 풀이를 진행 한다면 시간 복잡도: bfs 탐색 O(nm) * 익은 토마토의 최대 개수 O(NM) = O(N^2M^2) 가 되어 시간초과 발생

처음에 익은 토마토를 queue에 모두 집어넣고 bfs 진행

마지막에 -1이 있는지 여부를 꼭 확인해야 함

 

응용3 - 시작점이 두 종류일 때

4179: 불!