[알고리즘 오답노트] BFS

BFS 유형 뽀개기

 

* 2차원 배열 입력 * 

 

1. 하나씩 띄어서 입력할 때

 cin >> n >> m;
  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++)
      cin >> board[i][j];

 

 

2. 붙어서 입력

cin >> n >> m;
  for(int i = 0; i < n; i++)
    cin >> board[i];

int a[10][10], n, m;
int main(){
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			scanf("%1d", &a[i][j]);
		}
	}

 

* reset 할 때 fill 함수 * 

  for(int i = 0; i < n; i++){
          fill(board[i], board[i]+m, 0);
          fill(vis[i], vis[i]+m, false);
        }

 

Basic

1. 같은 섬끼리의 넓이 구하기 

[백준 1926] 그림 (tistory.com)

 

cnt(각각 섬 카운팅), area(섬의 최대 넓이 구할 용) 변수 두개 필요

max 함수 쓰는법 

marea=max(marea,area); 이게 실제 바뀌는 값.

check[][] 배열 bool이니까 숫자 넣지 말고 ==false? ==true? 

 

*주의할점*

cnt와 area가 어느 지점에 들어가야 하는지 생각해야함

처음 들어갈때  if(a[i][j]==1&&check[i][j]==false) 여기 다음엔 cnt++ ( 섬 하나 처음 들어가는 부분)

area는 섬 하나 안에서 자리 옮길때마다 +1 해주는것이니까

while문 나가고(q가 empty일 때) 다른 섬으로 이동하기 전에 max area 체크해주고 

area는 본격적으로 +1씩 되기 직전에 int area=0;

 

 

2.  최단거리 구하기

[백준 2178] 미로 탐색 (tistory.com)

 

보통 실제 입력맵 a[][] 과 방문했는지 체크하는 bool vis[][] 두개를 두고 쓰지.

근데 조건이 더 있다? 최단거리를 구한다? 배열을 하나 더 둬. 뭐가 더 필요하면 배열을 하나 더 두던가 3차원 배열로 만드는 아이디어가 필요해.

최단거리는 어차피 오른쪽 맨 마지막 칸에 숫자가 담기니까  cout<<dist[n-1][m-1]; 이렇게 출력하기

 

 

Intermediate

3. 시작점이 여러개

 

[백준 7576] 토마토 (DFS/BFS) (tistory.com)

 

- 모든 시작점을 큐에 넣고 BFS를 돌린다.

 

[백준 4179] 불! (tistory.com)

[백준 4179] 불!

- 불 문제처럼 @,#, . 등을 입력받을 때 주의할점은 입력 배열을 char 배열로 해야한다는 것

ex. char board[1000][1000];

 

- BFS를 두번 각각 돌리고 돌린 dist배열끼리 비교한다

 

4. 단순 BFS 두번

- BFS 두번 해줄 경우 vis 함수 같이 쓰면 fill 해서 리셋해주는 것 잊지 말기

 

이 문제 개인적으로 풀이가 깔끔하고 아이디어도 좋은듯 

[백준 10026] 적록색약 (tistory.com)

 

 

 

5. 1차원 BFS

[백준 1679] 숨바꼭질 (tistory.com)

 

- 1차원 연습 할 때 복습하기

 for(int nxt : {x-1, x+1, 2*x}){
          if(nxt < 0 || nxt > 100000) continue;
          if(dist[nxt] != -1) continue;
          dist[nxt] = dist[x]+1;
          Q.push(nxt);
        }

 

 

 

Advanced

 

6. 3차원 BFS

- 쫄지 말자 

- tuple 써서 구현하면 똑같음

[백준 7569] 토마토 (tistory.com)

 

 queue<tuple<int,int,int>> q;
            q.push({0,0,0});
         
          while(!q.empty())
          {
              int x,y,broken;
              tie(x,y,broken)=q.front();
              
          }

 

 

7. 예외 조건

ex. 이동 중 한번만 벽을 부술 수 있음

dist[x][y][0] //벽을 하나도 부수지 않고 (x,y)까지 오는데 걸리는 비용
dist[x][y][1] //벽을 하나만 부수고 (x,y)까지 오는데 걸리는 비용, (x,y)가 벽이라서 부수는 경우 포함

* bool check 하거나

* 3차원 배열 만들거나

* BFS를 두번 돌리거나(vis1[][], vis2[][])

 

[백준 2206] 벽 부수고 이동하기 (tistory.com)

 

 

 

 

 

문제 풀이 연습

basic-algo-lecture/0x09.md at master · encrypted-def/basic-algo-lecture (github.com)