[백준] 1260번 : DFS와 BFS (실버Ⅱ) by node.js

▷ 문제 :1260번 : DFS와 BFS 

1260번: DFS와 BFS

▷ 해결 날짜 : 2022.04.04
▷ 소요 시간 : 2시간 30분
▷ 풀이 과정 :

문제는 너무나도 기본 문제라 아 그냥 DFS와 BFS를 사용해서 풀어보라는구나 싶을 정도의 내용이었다.

이 문제에서 중요한 건 기본적인 DFS와 BFS의 개념이고

• 입력으로 주어지는 간선은 양방향이다.
• 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다.
• 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다.

이것들만 주의해주면 된다. 

 

우선 조건에 맞게 bfs에서는 큐 구조로 shift를 사용하기 때문에 오름차순, dfs는 스택 구조로 pop을 사용하기 때문에 내림차순으로 구현하였다.

 

그리고 입력값을 뽑아서 인접 리스트 그래프를 만들고 DFS와 BFS 알고리즘을 실행시켜주는 게 코드의 전부이다.

 

▷ 구현

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

const bfs = (graph, startNode) => {
  const visited = [];
  let needVisit = [];

  needVisit.push(startNode);

  while(needVisit.length !==0){
    const node = needVisit.shift();
    if(!visited.includes(node)){
      visited.push(node);
      let nodes = graph[node];
      needVisit = [...needVisit, ...nodes.sort((a, b) => a - b)];
    }
  }

  return visited;
};

const dfs = (graph, startNode) => {
  const visited = [];
  let needVisit = [];

  needVisit.push(startNode);
  while(needVisit.length !==0){
    const node = needVisit.pop();
    if(!visited.includes(node)){
      visited.push(node);
      let nodes = graph[node];
      needVisit = [...needVisit, ...nodes.sort((a, b) => b - a)];
    }
  }

  return visited;
};

let [n, edge, start] = input.shift().split(' ').map(Number);
let grph = [...Array(n + 1)].map(e => []);

for(let i = 0 ; i < edge ; i++){
    let [from, to] = input[i].split(' ').map(Number);
    grph[from].push(to);
    grph[to].push(from);
}

console.log(dfs(grph, start).join(' '));
console.log(bfs(grph, start).join(' '));

 

▷ 복기 :

그래프 알고리즘을 공부 시작할 겸 개념을 먼저 익히고 그걸 실전에서 익혀보려고 시작한 문제였다.

백준에서 사용되는 DFS와 BFS 알고리즘 기초 문제이며, 딱 지금 내 수준에서 풀기 좋은 문제라 생각해 시작해봤다.

 

하지만 역시 너무 어려웠다... 어려운 건 다름 아니라 틀렸을 경우 반례를 도저히 찾을 수가 없다는 점이다.

이 문제에서 시간이 굉장히 많이 소비됐는데 사실 1시간도 안 걸려서 풀었던 문제인데 마지막 출력 부분에서

join(' ')을 놓치는 바람에 2시간 가까이 헤맸다...

 

질문 게시글의 모든 반례를 시도해도 너무 출력이 잘 나오고 그랬는데 알고 보니 출력이 [1, 2, 3, 4]가 아니라 "1, 2, 3, 4" 였던 것을 놓치고 말았다 하하하...

 

그래서 처음에는 코드가 잘못된 줄 알고 인터넷 검색을 해봐도 다들 인접 행렬로만 푼 문제만 있어서 크게 도움이 되지는 않았다 그리고 다들 어디서 보고 풀었는지 똑같은 코드가 너무 많았다.

 

위 코드는 인접 리스트로 푼 방식이다.

 

그래도 시간이 오래 걸렸지만 백준 문제나 그래프 알고리즘이나 제대로 스타트를 끊은 느낌이다.