[Javascript] 백준 1260: DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1 

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1 

1 2 4 3
1 2 3 4

예제 입력 2 

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2 

3 1 2 5 4
3 1 4 2 5

예제 입력 3 

1000 1 1000
999 1000

예제 출력 3 

1000 999
1000 999

 

---

문제 요약

- 입력으로 양방향 간선(노드끼리 연결하는 선)이 주어지면, DFS와 BFS 순서대로 출력하기

 

풀이 방법

1) 인접행렬 구하기

• 인접행렬은 노드간 연결이 되어있으면 1, 연결되어있지 않으면 0으로 표기하는 2차원 배열이다.
• 예제 1번의 입력값을 이용해 인접행렬을 만들면 아래와 같은 모습이다.
• index가 0부터 시작하기 때문에 헷갈리지 않도록 4X4 행렬이 아닌 5X5 행렬로 만들었다.

[
  [ 0, 0, 0, 0, 0 ],
  [ 0, 0, 1, 1, 1 ],
  [ 0, 1, 0, 0, 1 ],
  [ 0, 1, 0, 0, 1 ],
  [ 0, 1, 1, 1, 0 ]
]

 

2) DFS 풀이법

- 한개의 행을 순회하면서 연결되어있고 방문하지 않은 노드를 만나면 정답배열에 푸시 

- 해당 노드로 재귀 호출 

=> 방문한 노드의 행으로 이동하여 반복

 

3) BFS 풀이법

- 행을 담은 queue 생성하여 해당 행을 다 순회하면 다음 행으로 넘어가도록 구현

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");


const [N, M, V] = input[0].split(" ").map(Number);

//인접행렬 구하기
const graph = Array.from(Array(N + 1), () => new Array(N + 1).fill(0));

for (let i = 1; i <= M; i++) {
  let [row, column] = input[i].split(" ").map(Number);
  graph[row][column] = 1;
  graph[column][row] = 1;
}

const DFS_visited = new Array(N + 1).fill(false);
const DFS_answer = [];
const BFS_visited = new Array(N + 1).fill(false);
const BFS_answer = [];

function DFS(V) {
  DFS_visited[V] = true;
  DFS_answer.push(V);
  for (let i = 1; i < graph.length; i++) {
    if (graph[V][i] === 1 && DFS_visited[i] === false) {
      DFS(i);
    }
  }
}

function BFS(V) {
  const queue = [];
  BFS_visited[V] = true;
  BFS_answer.push(V);
  queue.push(V);

  while (queue.length !== 0) {
    let dequeue = queue.shift();
    for (let i = 1; i < graph.length; i++) {
      if (graph[dequeue][i] === 1 && BFS_visited[i] === false) {
        BFS_visited[i] = true;
        queue.push(i);
        BFS_answer.push(i);
      }
    }
  }
}

DFS(V);
BFS(V);

console.log(DFS_answer.join(" "));
console.log(BFS_answer.join(" "));