[백준] 단지 번호 붙이기

in 코딩테스트 on 백준




96. 예상 대진표

백준

bfs/dfs에 대해 강해지자!!
다른 분의 솔루션을 참고했다…ㅠㅠ 배열에서 어떻게 연결된 애를 이을지 몰랐었다.
moveRow, moveCol 이라는 변수를 만들어서 동서남북 움직임 기준을 알려준다. 잊지말기

dfs

function solution(n, arr) {
  let number = 0;
  let result = [];
  let visited = [];
  for (let i = 0; i < n; i++) {
    visited.push([]);
    for (let j = 0; j < n; j++) {
      visited[i].push(0);
    }
  }

  let check = (row, col) => {
    if (row >= 0 && row < n && col >= 0 && col < n) {
      return true;
    }
    return false;
  };

  let moveRow = [0, 0, 1, -1];
  let moveCol = [1, -1, 0, 0];

  function dfs(row, col) {
    if (
      check(row, col) === true &&
      arr[row][col] === 1 &&
      visited[row][col] === 0
    ) {
      visited[row][col] = 1;
      number++;
      for (let n = 0; n < moveRow.length; n++) {
        dfs(row + moveRow[n], col + moveCol[n]);
      }
    } else {
      return;
    }
  }

  for (let row = 0; row < n; row++) {
    for (let col = 0; col < n; col++) {
      if (arr[row][col] === 1 && visited[row][col] === 0) {
        dfs(row, col);
        result.push(number);
        number = 0;
      }
    }
  }

  result.sort((x, y) => x - y);
  return [result.length, ...result];
}

let arr = [
  [0, 1, 1, 0, 1, 0, 0],
  [0, 1, 1, 0, 1, 0, 1],
  [1, 1, 1, 0, 1, 0, 1],
  [0, 0, 0, 0, 1, 1, 1],
  [0, 1, 0, 0, 0, 0, 0],
  [0, 1, 1, 1, 1, 1, 0],
  [0, 1, 1, 1, 0, 0, 0],
];

console.log(solution(7, arr));

bfs

function solution(n, arr) {
  let visited = [];
  for (let i = 0; i < n; i++) {
    visited.push([]);
    for (let j = 0; j < n; j++) {
      visited[i].push(0);
    }
  }

  let moveRow = [0, 0, 1, -1];
  let moveCol = [1, -1, 0, 0];
  let number = 0;
  let result = [];

  let check = (row, col) => {
    if (row >= 0 && row < n && col >= 0 && col < n) {
      return true;
    }
    return false;
  };

  let bfs = (row, col) => {
    let queue = [];
    queue.push([row, col]);
    while (queue.length) {
      let vertex = queue.shift();
      let row = vertex[0];
      let col = vertex[1];
      if (visited[row][col] === 0) {
        visited[row][col] = 1;
        number++;
        for (let i = 0; i < moveRow.length; i++) {
          if (
            check(row + moveRow[i], col + moveCol[i]) &&
            arr[row + moveRow[i]][col + moveCol[i]] === 1
          ) {
            queue.push([row + moveRow[i], col + moveCol[i]]);
          }
        }
      }
    }
  };

  for (let row = 0; row < n; row++) {
    for (let col = 0; col < n; col++) {
      if (arr[row][col] === 1 && visited[row][col] === 0) {
        bfs(row, col);
        result.push(number);
        number = 0;
      }
    }
  }

  result.sort((x, y) => x - y);
  return [result.length, ...result];
}

let arr = [
  [0, 1, 1, 0, 1, 0, 0],
  [0, 1, 1, 0, 1, 0, 1],
  [1, 1, 1, 0, 1, 0, 1],
  [0, 0, 0, 0, 1, 1, 1],
  [0, 1, 0, 0, 0, 0, 0],
  [0, 1, 1, 1, 1, 1, 0],
  [0, 1, 1, 1, 0, 0, 0],
];

console.log(solution(7, arr));