Algorithm/BOJ

[알고리즘/백준/1260] DFS와 BFS(비교)

2023. 5. 21. 14:39
목차
  1. 문제
  2.  
  3. 풀이
반응형

문제


https://www.acmicpc.net/problem/1260

 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net

 

풀이


const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let [nums, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");

const [n, m, v] = nums.split(" ").map(Number);
const pairs = arr.map((pair) => pair.split(" ").map(Number));
let graph = Array.from({ length: n + 1 }, () => []);
let dfsPath = [];
let bfsPath = [];

// 인접 리스트
for (let [s, e] of pairs) {
  graph[s].push(e);
  graph[e].push(s);
}

graph = graph.map((v) => v.sort((a, b) => a - b));

function getDFSPath(v) {
  let ch = Array.from({ length: n + 1 }, () => 0);
  ch[v] = 1;
  dfsPath.push(v);

  function DFS(v) {
    for (let i = 0; i < graph[v].length; i++) {
      const nv = graph[v][i];
      if (ch[nv] === 0) {
        ch[nv] = 1;
        dfsPath.push(nv);
        DFS(nv);
      }
    }
  }

  DFS(v);
}

function getBFSPath(v) {
  let q = [];
  let ch = Array.from({ length: n + 1 }, () => 0);

  ch[v] = 1;
  bfsPath.push(v);
  q.push(v);

  while (q.length) {
    const v = q.shift();
    for (let i = 0; i < graph[v].length; i++) {
      const nv = graph[v][i];
      if (ch[nv] === 0) {
        ch[nv] = 1;
        bfsPath.push(nv);
        q.push(nv);
      }
    }
  }
}

getDFSPath(v);
getBFSPath(v);

console.log(dfsPath.join(" "));
console.log(bfsPath.join(" "));

입력 받은 그래프를 연결 되어 있는 노드 배열을 for문으로 돌면서 인접 리스트로 만든다.

DFS는 각 노드에 연결되어 있는 노드를 순회하면서 (graph[v].length) 다음 노드(nv)가 방문하지 않은 노드인 경우(if(ch[nv] === 0) 해당 노드로 바로 이동(DFS(nv))한다.

반면 BFS는 각 노드에 연결되어 있는 노드를 순회하면서 다음 노드가 방문하지 않은 노드인 경우 q에 넣고 대기한다. 동일 레벨에 있는 노드들을 모두 방문하고 난 다음에야 q에 넣어둔 노드(연결되어 있는 노드)를 방문한다.

반응형
저작자표시

'Algorithm > BOJ' 카테고리의 다른 글

[알고리즘/백준/2667] 단지 번호 붙이기  (1) 2023.05.23
[알고리즘/백준/1325] 효율적인 해킹(BFS, JavaScript, 백준 Nodejs로 풀 때 유의사항)  (4) 2023.05.22
[알고리즘/백준/2178] 미로탐색(BFS, 최단거리)  (1) 2023.05.22
[알고리즘/백준/11725] 트리의 부모 찾기(DFS, BFS, 백준 console 시간 초과 해결)  (0) 2023.05.21
[알고리즘/백준/2606] 바이러스  (0) 2023.05.21
  1. 문제
  2.  
  3. 풀이
'Algorithm/BOJ' 카테고리의 다른 글
  • [알고리즘/백준/1325] 효율적인 해킹(BFS, JavaScript, 백준 Nodejs로 풀 때 유의사항)
  • [알고리즘/백준/2178] 미로탐색(BFS, 최단거리)
  • [알고리즘/백준/11725] 트리의 부모 찾기(DFS, BFS, 백준 console 시간 초과 해결)
  • [알고리즘/백준/2606] 바이러스
개발자 김비숑
개발자 김비숑
프론트엔드 개발자를 준비하고 있는 김비숑입니다.
김비숑과 프론트엔드프론트엔드 개발자를 준비하고 있는 김비숑입니다.
반응형
개발자 김비숑
김비숑과 프론트엔드
개발자 김비숑
전체
오늘
어제
  • 분류 전체보기 (118)
    • FrontEnd (24)
      • HTML&CSS (1)
      • JavaScript (3)
      • TypeScript (8)
      • React (8)
      • Test (4)
    • CS (1)
    • Algorithm (83)
      • BOJ (42)
      • Inflearn (26)
      • Programmers (15)
    • Git (0)
    • Projects (4)
    • Translation (1)
    • Others (0)
      • Reviews (4)
      • About Me (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 글쓰기

인기 글

최근 글

hELLO · Designed By 정상우.
개발자 김비숑
[알고리즘/백준/1260] DFS와 BFS(비교)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.