[구름톤 챌린지] 연합 (JS)

풀이 과정

1. 섬 번호를 키, 연결된 섬 배열을 값으로 하는 객체 생성
2. 각 섬의 연결 상태를 표현하는 2차원 배열(행렬) 생성
3. 연합 번호를 값으로 가지는 visited 배열 생성
4. 각 섬에 대해 반복
5. bfs로 현재 섬에서 갈 수 있는 경로를 탐색하면서 같은 연합 번호로 visited 설정
   이때 쌍방 연결되고 다음에 갈 섬이 visited가 아니면 연합이 가능한 섬

코드

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

rl.on('close', () => {
  const obj = {};
  const matrix = Array(N + 1)
    .fill(0)
    .map((_) => Array(N + 1).fill(false));
  for (let i = 1; i <= M; ++i) {
    const [s, e] = input[i];
    if (!obj[s]) obj[s] = [];
    obj[s].push(e);
    matrix[s][e] = true;
  }

  const visited = Array(N + 1).fill(0);
  let result = 1; // 현재 연합 번호
  for (let i = 1; i <= N; ++i) {
    if (visited[i]) continue; // 이미 연합에 속해 있으면 넘어가기
    const q = [i]; // 탐색 후보 큐
    while (q.length) {
      const curr = q.shift();
      visited[curr] = result;
      if (!obj[curr]) continue; // 연결된 섬이 없으면 넘어가기
      for (const next of obj[curr]) {
        if (!obj[next]) continue; // 연결된 섬이 없으면 넘어가기
        if (!matrix[next][curr] || visited[next]) continue; // 쌍방 연결이 아니거나 이미 연합에 속해 있으면 넘거가기
        q.push(next);
      }
    }
    ++result;
  }

  console.log(result - 1);
  process.exit();
});

🤔

행렬로도 해보고 리스트로도 해보고 섞어서도 해보는데 1시간 동안 해결이 안 됐다. 통과를 못하는 테스트 케이스가 너무 많다... 뭘 놓친 걸까. 내일 해설 보고 다시 해봐야겠다.

09/05 해설 참조 후 추가
이게 BFS구나...
연결된 섬끼리 연합이 된다는 게 결국에는 '갈 수 있는 모든 곳을 탐색한다'였다.
이런 문제는 정말 많이 풀어보면서 감을 잡는 수밖에 없는 것 같고, 아직은 내 힘만으로 풀기 힘든 수준인 것 같다.