Portfolio

정다윤 풀이


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

const node = Number(input[0].split(" ")[0]);
const edge = Number(input[0].split(" ")[1]);
const start = Number(input[0].split(" ")[2]);

const graph = [...new Array(node + 1)].map(() => []);
const visited = [...new Array(node + 1)].fill(0);

for (let i = 0; i < edge; i++) {
  const [start, end] = input[i + 1].split(" ").map(Number);
  graph[start].push(end);
  graph[end].push(start);
}

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

/** dfs */

let ansDfs = [start];
visited[start] = 1;
function dfs(start) {
  for (let end of graph[start]) {
    if (!visited[end]) {
      ansDfs.push(end);
      visited[end] = 1;
      dfs(end);
    }
  }
}

dfs(start);

console.log(ansDfs.join(" "));

/** bfs */
visited.fill(0);
visited[start] = 1;
let ansBfs = [start];
const bfs = [start];

while (bfs.length) {
  let end = bfs.shift();

  graph[end].forEach((e) => {
    if (!visited[e]) {
      bfs.push(e);
      visited[e] = 1;
      ansBfs.push(e);
    }
  });
}

console.log(ansBfs.join(" "));

김민수 풀이


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

const [N, M, V] = input.shift().split(' ').map(Number);
input = input.map(e => e.trim().split(' ').map(Number));

let graph = Array.from({length:N+1}, () => []);
let visited = Array.from({length:N+1}, () => false);
visited[V] = true;
let [dfsResult, bfsResult] = [[],[]];

for(const [a, b] of input){
  graph[a].push(b);
  graph[b].push(a);
}

const bfs = (visited) => {
  let queue = [];
  queue.push(V);
  
  while(queue.length !== 0){
    const v = queue.shift();
    for(const node of graph[v].sort((a,b) => a - b)){
      if(!visited[node]){
        queue.push(node);
        bfsResult.push(node);
        visited[node] = true;
      }
    }
  }
}

const dfs = (list) => {
  list.sort((a,b) => a - b).forEach(e => {
    if(!visited[e]){
      visited[e] = true;
      dfsResult.push(e);
      dfs(graph[e]);
    }
  })
}

bfs([...visited]);
dfs(graph[V]);    // 둘이 순서 바뀌면 visited 넣어야됨.. 귀찮

console.log(V , dfsResult.join(' ') + '\n' + V , bfsResult.join(' '));

하송희 풀이


const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let [info, ...edges] = fs.readFileSync(filePath).toString().trim().split("\n");
let [n, m, v] = info.split(" ");
let graph = new Array(+n + 1).fill().map(() => []);
let visited = new Array(+n + 1).fill(0);
let dfsArr = [];
let bfsArr = [];

const dfs = (v) => {
  if (visited[v] == true) return;

  visited[v] = 1;
  dfsArr.push(+v);

  for (let i = 0; i < graph[v].length; i++) {
    let next = graph[v][i];
    if (visited[next] == 0) dfs(next);
  }
};

const bfs = (v) => {
  let queue = [+v];

  while (queue.length > 0) {
    let cur = queue.shift();

    if (visited[cur] == 1) continue;
    visited[cur] = 1;
    bfsArr.push(cur);

    for (let i = 0; i < graph[cur].length; i++) {
      let next = graph[cur][i];
      if (visited[next] == 0) queue.push(next);
    }
  }
};

const result = (v) => {
  for (let i = 0; i < +m; i++) {
    let [from, to] = edges[i].split(" ");
    graph[from].push(+to);
    graph[to].push(+from);
  }
  graph.forEach((ele) => {
    ele.sort((a, b) => a - b);
  });

  dfs(v);
  console.log(dfsArr.join(" "));

  visited.fill(0);

  bfs(v);
  console.log(bfsArr.join(" "));
};

result(v);

안재현 풀이

이승민 풀이


function dfs(graph, start, dfsVisit) { //재귀
    dfsVisit[start] = true;

    dfsResult.push(start);
    for (const node of graph[start]) {
        if (!dfsVisit[node]) {
            dfs(graph, node, dfsVisit);
        }
    }
    return;
}

function bfs(graph, start) {
    const bfsVisit = new Array(n + 1).fill(false);
    const q = [];
    let bfsResult = [start];

    q.push(start);

    while (q.length) {
        const k = q.shift();
        bfsVisit[k] = true;

        for (const node of graph[k]) {
            if (!bfsVisit[node]) {
                q.push(node);
                bfsVisit[node] = true;
                bfsResult.push(node);
            }
        }
    }

    return bfsResult.join(' ');
}


let fs = require('fs');

//const inputs = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const inputs = fs.readFileSync(__dirname+'/ex2.txt').toString().split('\n');

const [n, m, v] = inputs[0].split(' ').map(Number);

let graph = [];
for (let i=1; i<=n; i++){
    graph[i] = [];
}

for (let i=1; i <= m; i++) {
    const [v1, v2] = inputs[i].split(' ').map(Number);

    graph[v1].push(v2);
    graph[v2].push(v1);
}

graph.forEach((element) => { //그래프 정렬
    element.sort((a, b) => a - b);
});

let dfsResult = [];

dfs(graph, v, []);
const bfsResult = bfs(graph, v);

console.log(dfsResult.join(' '));
console.log(bfsResult);

3. DFS와 BFS

정다윤 풀이

김민수 풀이

하송희 풀이

안재현 풀이

이승민 풀이