코딩테스트 - BFS

개념

그래프 탐색 : 어떤것들이 연속해서 이어질때, 모두 확인하는 방법

• Graph : Vertex(어떤것) + Edge(이어지는것)

아이디어

• 시작점에 연결된 Vertex찾기
• 찾은 Vertex를 Queue에 저장
• Queue의 가장 먼저 것 뽑아서 반복

시간복잡도

• O(V+E)

자료구조

• 검색할 그래프
• 방문여부 확인(재방문 금지)
• Queue: BFS실행

백준 문제 : 1926

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

ex)
input :
6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

output :
4
9

풀이

//백준에서는 입력값을 직접 받는다.
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on("line", function (line) {
  input.push(line);
  //ctrl+D를 입력하면 입력 종료
}).on("close", () => {
  /*
  1. 아이디어
  - 2중 for => 값 1 && 방문X => BFS
  - BFS 돌면서 그림 개수  +1, 최대값을 갱신

  2. 시간복잡도
  - BFS: O(V+E)
  - v: 500 * 500
  - e: 4 * 500 * 500
  - V+E = 5 * 250000 = 1000000 <= 2억

  3. 자료구조
  - 그래프 전체지도 : int[][]
  - 방문 : bool[][]
  - Queue(BFS)
*/

  //y, x 에 대한 입력값을 배열로 만듬
  const [n, m] = input[0].split(" ").map(Number);
  const map = [];
  //y 기준으로 이중배열을 만듬
  for (let i = 1; i <= n; i++) {
    map.push(input[i].split(" ").map(Number));
  }
  //방문노드
  const chk = Array.from({ length: n }, () => Array(m).fill(false));

  let cnt = 0; //전체 그림 숫자
  let size = 0; //최대 크기 

  //오른쪽,아래,왼쪽,위쪽
  let dy = [0, 1, 0, -1];
  let dx = [1, 0, -1, 0];

  //2. 방문한 위치로부터 사이즈를 구한다.
  function bfs(y, x) {
    let res = 1;
    let q = [[y, x]];
    while (q.length > 0) {
      let [ey, ex] = q.shift(); // 배열의 첫 번째 요소를 제거하고 반환

      //우하좌상을 모두 검사
      for (let i = 0; i < 4; ++i) {
        let ny = ey + dy[i];
        let nx = ex + dx[i];
        if (0 <= ny && ny < n && 0 <= nx && nx < m) {
          if (map[ny][nx] == 1 && chk[ny][nx] == false) {
            res++;
            chk[ny][nx] = true;
            q.push([ny, nx]); // 올바른 배열 형식으로 push
          }
        }
      }
    }

    return res;
  }

  //1. 이중 for문 돌면서 진입 가능한 위치를 찾는다
  for (let j = 0; j < n; ++j) {
    for (let i = 0; i < m; ++i) {
      //값이 1이면서 방문하지 않은 위치
      if (map[j][i] == 1 && chk[j][i] == false) {
        //방문처리
        chk[j][i] = true;
        //전체 그림 숫자 +1
        cnt++;
        //최대값 갱신 = bfs()를 돌면서 최대값을 비교
        size = Math.max(size, bfs(j, i));
      }
    }
  }

  console.log(cnt);
  console.log(size);
});

알아야할 것

• 2중 for loop => 일때는 y부터 돌아야 한다
• BFS는 Queue 자료구조를 쓸 것