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

풀이 과정

1. 지도에 1이 없어질 때까지 반복
2. 1을 찾아서 상하좌우 탐색 시작 (탐색 배열에 현재 위치 담기)
   이때 발전기 개수 +1
3. 다음 길이 1이면 방문 표시(0으로 갱신)
   이때 탐색 배열의 현재 위치(마지막 요소)의 방향 갱신, 탐색 배열에 다음 길 위치 담아서 이동
   다음 길이 0이면 넘어가기
4. 더이상 이동할 길이 없으면 탐색 배열 pop

코드

// Run by Node.js
const readline = require('readline');

(async () => {
  let rl = readline.createInterface({ input: process.stdin });

  const input = [];
  for await (const line of rl) {
    input.push(line.trim());
    if (input.length === Number(input[0]) + 1) {
      rl.close();
    }
  }

  const N = Number(input[0]);
  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 dx = [0, 1, 0, -1];
  const dy = [1, 0, -1, 0];

  let result = 0;
  for (let i = 0; i < N; ++i) {
    for (let j = 0; j < N; ++j) {
      if (arr[i][j] !== 1 || visited[i][j]) continue;
      ++result;
      const tmp = [[i, j]];

      while (tmp.length) {
        let [currI, currJ] = tmp.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] !== 1 || visited[ni][nj]) continue;
          tmp.push([ni, nj]);
        }
      }
    }
  }
  console.log(result);
  process.exit();
})();

🤔

진짜 너무 어려워요 갑자기 🫠
풀이 과정 생각하는 데 거의 1시간, 디버깅에 거의 3-40분을 썼는데 제출하면 테스트 케이스 반 정도가 타임아웃이 난다. 근데 지금은 다른 풀이 방식을 떠올리지 못하겠다. 시간을 너무 많이 써서 내일 풀이 확인하고 다시 해보는 걸로. 결국 3주차부터 따라가지 못하기 시작했군. 코테 조무래기로서 2주차까지 해설 없이 해왔던 것도 나름 뿌듯하긴 하다.

08/30 해설 참조 후 추가
완전 탐색과 달리 '가능한' 모든 경로를 탐색하는 걸 너비 우선 탐색(BFS)라고 한다는데, 매번 그런 게 있다고만 들었지 이제야 그게 뭔지 알게 됐다. 접근 방법 자체는 유사했으니 만족... 무튼 바로 arr 배열을 수정하지 않고 visited를 만들어서 방문 여부를 확인하도록 수정했다. 또 이동할 수 있는 경로가 없을 때만 pop을 했었는데 그게 아니라 일단 방문한 곳은 넣고 pop 이게 큰 차이였던 것 같다.