[Baekjoon (Node.js)] 24479번 알고리즘 수업 - 깊이 우선 탐색 1

📄 문제

문제 사진

입출력 예제

---

📝 나의 통과 풀이

let input = require("fs")
  .readFileSync("/dev/stdin") // /dev/stdin
  .toString()
  .split("\n")
  .map((item) => item.replace("\r", ""));

let [N, M, R] = input.shift().split(" ").map(Number);

class Graph {
  constructor() {
    this.nodes = {};
    this.count = 1;
    this.visited = [];
    this.result = [];
    for (let i = 0, j = N; i < j + 1; i++) {
      this.visited[i] = 0;
    }
    for (let i = 0, j = N; i < j; i++) {
      this.result[i] = 0;
    }
  }

  addNode(node) {
    this.nodes[node] = {} || [];
  }

  addEdge(fromNode, toNode) {
    this.nodes[fromNode][toNode] = true;
    this.nodes[toNode][fromNode] = true;
  }

  DFS(start) {
    this.visited[start] = 1;
    this.result[start - 1] = this.count++;
    if (!this.nodes[start] == {}) {
      return;
    }

    for (let [key, value] of Object.entries(this.nodes[start])) {
      if (!this.visited[key]) {
        this.DFS(key);
      }
    }

    return this.result;
  }
}

let seokhoGraph = new Graph();
for (let i = 1; i <= N; i++) {
  seokhoGraph.addNode(i);
}
for (let j = 0; j < M; j++) {
  let target = input[j].split(" ");
  let [from, to] = target;
  seokhoGraph.addEdge(from, to);
}

console.log(seokhoGraph.DFS(R).join("\n"));

아니 이거 기본 문제 인줄 알았다가 엄청 고생했다...

---

⌨ 접근법

1. 입력을 잘라서 [정점, 간선, 시작 정점] 배열 [N, M, R] 을 만든다.

2. class 문법으로 그래프를 만든다.

3-1.구성 함수 : (정점 추가, 간선 추가, DFS 함수)

3-2 구성 변수 : (루프 카운트 : count, 방문 확인용 array : visited, 결과를 담을 array:  result)

4. DFS를 돌리면 시작 정점 R 부터 함수가 돌며 result 방문 완료 index에 count를 올리면서 넣어준다.

5. 함수의 return 값은 배열로 들어가므로 마지막에 join('\n') 해서 한줄씩 나오는 문자열을 완성한다.

---

😤 스토리 ㅜㅜ 

- 이 문제는 이야기 하자면 정말 길다. 

 

- 결과는 잘 나오는데 왜 통과가 안될까... 알고보니 문제를 잘못 이해한 것이었고, 문제를 잘 파악하니 실행 시간 초과가 나오고, 형식을 바꿔가며 이것 저것 고쳐봐도 계속해서 실패...

 

- 이 문제는 팀원 'BOB'의 공이 정말 크다. 상세하게 그래프 생성, array || object || Map 코드 구현 및 속도 체크, 루프 로직 효율 체크 등 정말 많은 노력을 들여 연구하고 우리에게 공유해주어서 겨우 풀 수 있었던 문제다 ㅜㅜ

 

- 팀원 모두 머리 아파했던 문제로 힘들었지만 너무 재밌는 문제였다!

 

뒤에 한페이지 더있다 죽여줘...

---

📚 문제 링크

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

24479번: 알고리즘 수업 - 깊이 우선 탐색 1