BFS/DFS 문제풀이 ( feat : 실버2)

DFS와 BFS

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

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

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

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

풀이 방향

(1) 2각 노드와 간선을 이용해서 ,2차원 배열을 생성
(2) DFS와 BFS 함수를 정의하고 , 노드 방향 정의

풀이

내 풀이

function solution(N, M, V, strings) {
  // console.log(strings);
  // 간선의 정보를 입력할 2차원 배열 생성
  const graph = Array.from(Array(N + 1), () => new Array(N + 1).fill(0));
  // 방문한 정점을 저장할 배열 생성
  // const dfsVisited = Array.from(Array(N + 1), () => 0);
  const dfsVisited = [];
  const bfsVisited = [];

  const sortedArr = strings
    .split(`\n`)
    .map((item) => item.split(" ").map((tem) => Number(tem)));

  //그래프 입력 정보
  sortedArr.forEach((element) => {
    graph[element[0]][element[1]] = 1;
    graph[element[1]][element[0]] = 1;
  });

  // V부터 시작
  function dfs(node) {
    // 방문 처리
    dfsVisited.push(node);
    for (let i = 1; i <= N; i++) {
      // 같은 노드는 패스
      if (graph[node][i] === 1 && !dfsVisited.includes(i)) {
        dfs(i); // Recursively visit connected node
      }
    }
  }
  dfs(V);

  function bfs(node) {
    // 큐에 노드 저장
    const queue = [node];
    // 방문한 노드 저장
    bfsVisited.push(node);

    // 큐에 대이터 없을 떄까지
    while (queue.length > 0) {
      // 제일 처음 노드 넣기
      const current = queue.shift();

      for (let i = 1; i <= N; i++) {
        // 그래프 상태 확인
        if (graph[current][i] === 1 && !bfsVisited.includes(i)) {
          // 방문한걸로 확인
          bfsVisited.push(i);
          // 큐에 저장
          queue.push(i);
        }
      }
    }
  }
  bfs(V);
  console.log("dfsVisited", dfsVisited);
  console.log("bfsVisited", bfsVisited);

  // const visited
}

// solution(
//   5,
//   5,
//   3,
//   `5 4
// 5 2
// 1 2
// 3 4
// 3 1`
// );

solution(
  4,
  5,
  1,
  `1 2
1 3
1 4
2 4
3 4`
);

정리

• 그림좌표가 아닌, 주어진 경로만 가지고 만들어서 푸는 문제인데 머리로 잘 그려지지는 않았다.
• DFS에는 조금 익숙해지는 것 같고, BFS가 큐를 이용하는다는 건 이론적으로 받아들였고 ,머릿속으로 어떻게 돌아가서 이 경로가 다 만들어지는지는 아직 잘 안그려진다.