강의

https://www.youtube.com/watch?v=ftOmGdm95XI&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=10

설명

BFS란? Breadth(폭) First Search 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

1. 현재 위치에서 상하좌우를 살펴보면서 방문해야할 곳이 있다면 방문했다는 표시 후 해당 위치를 큐에 넣음.
2. 큐를 pop함. 이 때 pop한 위치에서 상하좌우를 살펴봤을 때 방문해야할 곳이 있다면 방문했다는 표시 후 해당 위치를 큐에 넣음.

이걸 큐가 empty할 때까지 반복

상하좌우를 탐색할 때 더 쉽게 하기 위해 dy, dx 배열을 이용하게 됨. 이 때 주의할 점은 기본적으로 생각하는 xy축이 아니라 아래와 같은 xy축을 가지고 함

https://what-am-i.tistory.com/77

따라서

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

를 이용하게 되면 남, 동, 북, 서 순서대로 탐색하게 되는 것

주의

시작점에 방문했다는 표시 남기기

큐에 넣을 때 방문했다는 표시를 남기기. 큐에서 빼낼 때 방문했다는 표시를 남기면 안 됨

이웃한 원소가 범위를 벗어났는지에 대한 체크 먼저 하고 접근하기.

문제

https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x09.md

1926

여기서 또 주의!! dx는 ↕ dy는 ↔

2178

board를 응용해서. board 인접한 애들의 거리는 board[cur.X][cur.Y] + 1

7576

시작점이 여러 개인 bfs. 그냥 시작점을 모두 queue에 놓고 시작하면 됨

1012

0,0부터 for문 돌면서 1인 애를 만나면 bfs함. 인접한 애들은 이미 1이 아니게 되기 때문에 bfs의 시작점만 1로 남게 됨. 마지막에 최종적으로 for문 돌면서 1인 애들을 세주면 답이 나옴.

7569

이번엔 삼차원. 상화좌우 + 윗칸 아래칸까지 고려해야함
tuple의 사용법과 tie 사용법을 알았다! pair<int, pair<int, int> > 할 필요 없이 tuple<int, int, int> 로 사용해주면 됨.
그리고 pair나 tuple 자료형을 tie로 묶어 한 번에 던져줄 수 있다.

auto cur;
int curZ, curX, curY;
tie(curZ, curX, curY) = cur

10026

처음엔 RGB 그대로 두고 bfs 한 다음 0인 부분 세어주면 적록색약 아닌 사람이 볼 수 있는 구역 개수가 나옴.
그 다음 G를 R로 바꾸고 B랑 G 구역을 bfs 해준 다음 0인 부분 세어주면 적록색약인 사람이 볼 수 있는 구역 개수가 나옴.

4179

jdist, fdist를 둬서 일반 bfs 조건에 jdist[cur.X][cur.Y] + 1 >= fdist[nx][ny]를 추가해주면 됨.

1697

2차원 bfs. 조건문 범위 조심!!!