구름톤 챌린지 4주차 학습 일기 - BFS(모든 섬 방문하는 문제)

모든 섬을 방문해야하는 문제이기 때문에, BFS로 문제를 해결할 수 있다. 

 

1. 그래프 입력

자바스크립트에서 그래프를 선언할 때는 인접 리스트 방식으로 그래프를 선언하고, 

이때 사용하는 자료구조는 객체이다. 

 

2. 연합의 개수 세기 위한 visited 변수 사용

visited는 섬의 방문 여부, 어떤 연합에 속해 있는지 확인할 수 있다. 

1. visited = Array(N + 1).fill(0); 로 visited의 모든 요소를 0으로 초기화 한다. 
2. visited[Node]의 값이 0이면, 그 섬은 어떤 연합에도 포함되지 않은 섬이다. 
3. 연합에 속하지 않는 섬에서, 새로운 연합을 만들었을 때 이를 i번 연합이라고 한다. 
4. i번 연합에 속한 섬들은 visited[Node] = i로 갱신한다. 

 

3. 조건대로 탐색하기

탐색의 조건은 아래와 같기 때문에 아래 조건을 동시에 확인하면 된다. 

1. 방문하지 않은 노드

2. 돌아오는 간선이 있는 노드 

 

4. Timeout 에러가 난다면 최적화하기

 

정답코드

처음에는 해결하지 못한 문제여서, 정답을 보고 난 후, 익일 다시 한 번 풀어보았다! 재도전했을 때는 정답이였다.

 

그래프를 만드는 것 까지는 이전에도 했었지만, 

1. 간선 여부를 나타내는 배열과

2. 방문 여부를 확인하는 배열

을 만드는 것이 포인트였다고 생각한다. 

const readline = require('readline');
let rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on('line', (line) => {
  input.push(line);
});

rl.on('close', () => {
  const [N, M] = input[0].split(' ').map(Number);
  const toFromArr = input.slice(1).map((el) => el.split(' ').map(Number));
  let check = Array.from(Array(N + 1), () => Array(N + 1).fill(false)); // 간선 여부를 나타내는 배열
  let visited = Array(N + 1).fill(0); // 방문 여부 확인하는 배열
  let obj = {};
  let count = 1;

  for (let i = 0; i < toFromArr.length; i++) {
    const [to, from] = toFromArr[i];

    if (!obj[to]) obj[to] = [];
    obj[to].push(from);
    check[to][from] = true;
  }

  for (let i = 1; i <= N; i++) {
    // 아직 방문하지 않았고,
    if (visited[i] === 0) {
      let q = [i];
      // 큐에 값이 없을 때까지 반복
      while (q.length > 0) {
        const currentNode = q.shift();
        // 방문했음을 표시
        visited[currentNode] = count;
        //* || [] 왜 하는거지? => 하지 않으면 runtime 에러 발생
        for (const nextNode of obj[currentNode] || []) {
          // 양방향 간선인지 확인 && 방문여부 확인
          if (check[nextNode][currentNode] && visited[nextNode] === 0) {
            // 조건에 만족한다면 다음 탐색 후보에 추가
            q.push(nextNode);
          }
        }
      }
      // 모든 연결된 노드 방문 후, 하나의 컴포넌트 완성되었으므로 count++
      count++;
    }
  }

  console.log(count - 1);

  rl.close();
});

 

참고자료

---

• 구름톤 프로젝트 매니징 자료