[구름톤 챌린지] 발전기 (JS)

풀이 과정

• 같은 유형의 건물이 2개 이상 이어져 있으면 단지
• 단지의 개수가 가장 많은 건물 유형 찾기

어제와 같은 BFS로 가능한 경로를 탐색해서 이어진 집을 찾아야 함
1. 마을의 각 요소에 대해 반복
2. visited 배열, 건물 유형을 키, 단지 수를 값으로 하는 객체 생성
3. 현재 요소의 건물 유형과 일치하고 visited가 아닌 곳을 방문
이때 pop할 때마다 개수를 세서 이어진 건물의 수 측정
이어진 건물의 수가 K개 이상이면 해당 건물 유형의 단지 수 +1
4. 가장 단지가 많은 유형 출력
이때 단지 수가 같으면 건물 유형이 큰 유형 출력

코드

const readline = require('readline');
let rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let input = [];
let N, K;
rl.on('line', (line) => {
  input.push(line.trim());
  [N, K] = input[0].split(' ').map(Number);
  if (input.length === N + 1) {
    rl.close();
  }
});

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

rl.on('close', () => {
  const arr = [];
  for (let i = 1; i <= N; ++i) {
    arr.push(input[i].split(' ').map(Number));
  }
  const visited = Array(N)
    .fill(0)
    .map((e) => Array(N).fill(false));
  const result = {};

  for (let i = 0; i < N; ++i) {
    for (let j = 0; j < N; ++j) {
      if (visited[i][j]) continue;
      const type = arr[i][j];
      const q = [[i, j]];
      let count = 1;

      while (q.length) {
        const [currI, currJ] = q.pop();
        visited[currI][currJ] = true;
        for (let k = 0; k < 4; ++k) {
          const ni = currI + dx[k];
          const nj = currJ + dy[k];
          if (ni < 0 || ni >= N || nj < 0 || nj >= N) continue;
          if (arr[ni][nj] !== type || visited[ni][nj]) continue;
          visited[ni][nj] = true;
          q.push([ni, nj]);
          ++count;
        }
      }
      if (count >= K) {
        result[type] = (result[type] || 0) + 1;
      }
    }
  }

  const sorted = Object.entries(result).sort(
    (a, b) => b[1] - a[1] || b[0] - a[0]
  );
  console.log(sorted[0][0]);
  process.exit();
});

🤔

BFS 알았으니까 코드가 술술 써져서 기분 좋았는데 테스트 케이스 몇 개가 통과를 못한다. 1시간 고민했으니 오늘은 여기까지~!

08/31 해설 참조 후 추가
깊이 우선 탐색(DFS)은 일단 한 방향으로 갈 수 있는 만큼 모든 탐색을 하고 갈 수 없는 경우 가장 가까운 갈림길로 돌아와서 다시 다른 방향으로 탐색하는 것이라고 한다.
BFS와 DFS의 시간복잡도는 같고 BFS는 큐, DFS는 스택이나 재귀 함수로 구현한다.
사실 아직 언제 뭘 써야 할지 잘 모르겠어서 문제를 많이 풀어봐야 할 것 같다.
모든 곳을 방문해야 하는 이 문제에서는 둘다 상관이 없다고 함
(다음 방문할 곳을 찾을 때 shift()를 쓰는지 pop()을 쓰는지의 차이)

사실 아직 잘 모르겠다. 너무 어렵다.