BFS 문제 풀이 ( feat: 그림 실버1 )

그림

https://www.acmicpc.net/problem/1926

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

입력
첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력
첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0이다.

풀이 방향

(1) 2중 for => 값 1 and false 값 찾기
(2) BFS 돌면서 그림 개수 +1 , 최대값을 갱신

풀이

내 풀이

function bfs1(H, R, strings) {
  let array = strings.split("\n").map((item) => {
    return item.split(" ").map((c) => {
      return { value: Number(c), visited: false };
    });
  });

  let result = [];

  /*
    2중 for 루프에서 방문하지 않은 1을 발견하면 BFS 수행
  */

  let dy = [0, 1, 0, -1];
  let dx = [1, 0, -1, 0];

  function bfs(y, x) {
    let count = 1;
    let queue = [{ y, x }];
    array[y][x].visited = true; // BFS 시작점 방문 표시

    while (queue.length > 0) {
      const { y: ey, x: ex } = queue.shift();
      for (let k = 0; k < 4; k++) {
        let ny = ey + dy[k];
        let nx = ex + dx[k];

        // 범위 내에 있으며, 1이면서 방문하지 않은 경우
        if (ny >= 0 && ny < H && nx >= 0 && nx < R) {
          if (array[ny][nx].value === 1 && array[ny][nx].visited === false) {
            array[ny][nx].visited = true; // 방문 표시
            count += 1;
            queue.push({ y: ny, x: nx });
          }
        }
      }
    }
    return count;
  }

  // i가 y축 , j가 x축
  for (let i = 0; i < H; i++) {
    for (let j = 0; j < R; j++) {
      // 1이고 아직 방문하지 않은 경우에 BFS 호출
      if (array[i][j].value === 1 && array[i][j].visited === false) {
        array[i][j].visited = true; // 방문 표시
        result.push(bfs(i, j));
      }
    }
  }

  console.log(result.length); // 그림의 개수 출력
  console.log(result.length > 0 ? Math.max(...result) : 0); // 최대 넓이 출력 (그림이 없으면 0)
}

bfs1(
  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`
);

GPT 개선 코드

• 방문 여부 배열 사용: array[y][x].visited와 같은 객체 접근 대신 visited라는 별도의 2차원 배열을 사용하면 속도와 가독성을 개선할 수 있습니다.
• 입력 값 파싱 최적화: strings.split("\n")로 전체 배열을 구성한 후, BFS를 돌면서 직접 1과 0을 비교해 방문 여부를 확인합니다.

function bfs1(H, R, strings) {
  const array = strings.split("\n").map((line) => line.split(" ").map(Number));
  const visited = Array.from({ length: H }, () => Array(R).fill(false));

  let pictureCount = 0;
  let maxArea = 0;

  const dy = [0, 1, 0, -1];
  const dx = [1, 0, -1, 0];

  function bfs(y, x) {
    let count = 1;
    let queue = [{ y, x }];
    visited[y][x] = true;

    while (queue.length > 0) {
      const { y: ey, x: ex } = queue.shift();
      for (let k = 0; k < 4; k++) {
        const ny = ey + dy[k];
        const nx = ex + dx[k];

        if (ny >= 0 && ny < H && nx >= 0 && nx < R) {
          if (array[ny][nx] === 1 && !visited[ny][nx]) {
            visited[ny][nx] = true;
            count += 1;
            queue.push({ y: ny, x: nx });
          }
        }
      }
    }
    return count;
  }

  for (let i = 0; i < H; i++) {
    for (let j = 0; j < R; j++) {
      if (array[i][j] === 1 && !visited[i][j]) {
        pictureCount += 1;
        const area = bfs(i, j);
        maxArea = Math.max(maxArea, area);
      }
    }
  }

  console.log(pictureCount); // 그림의 개수 출력
  console.log(maxArea);       // 최대 넓이 출력
}

bfs1(
  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`
);

정리

• BFS 알고리즘은 큐로 돌아가는 구조인데, 아직 어떻게 2차원 배열을 돌면서, 체크되는지 그림이 잘 안그려진다 .좀 더 적응해나가야겠다.