백준 1260 : DFS와 BFS

💡기본 정보

유형
: DFS/BFS
풀이 날짜
: 2025년 01월 20일 
풀이방법 한줄 요약
: 각자 DFS와 BFS로 탐색한 결과 계산해서 구현

 

💡문제에서 구해야 할 것

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성
방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문 + 더 이상 방문할 수 있는 점이 없는 경우 종료
정점 번호는 1번부터 N번까지 
- 입력 : 첫째 줄에 정점의 개수 N , 간선의 개수 M, 탐색을 시작할 정점의 번호 V가 주어짐
            다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어짐 . 어떤 두 정점 사이에 여러개의 간선이 있을 수 있음 

- 출력 : 첫째 줄에 DFS를 수행한 결과 
            둘째 줄에 BFS를 수행한 결과 V부터 방문된 점을 순서대로 출력

 

💡알고리즘 설계

-DFS구현
 : 현재 노드에서 노드 i로 연결된 간선 확인 + 이미 방문한 노드를 방문하지 않도록 함
-BFS구현
 : 큐를 활용해서 노드 i로 연결된 간선 확인 + 이미 방문한 노드를 방문하지 않도록 함

 

💡CODE

const fs = require("fs");
const input = fs.readFileSync(0,"utf8").toString().split("\n");
const [N,M,V] = input[0].split(" ").map(Number);
let graph = Array(N+1);
for(let i = 0; i<graph.length;i++){
    graph[i]=[];
}

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

const DFSvisit = new Array(N+1).fill(false);
const Danswer = [];
const BFSvisit = new Array(N+1).fill(false);
const Banswer = [];

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

function BFS(V){
    BFSvisit[V]=true;
    Banswer.push(V);
    const queue =[];
    queue.push(V);

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

DFS(V);
BFS(V);

console.log(Danswer.join(" "));
console.log(Banswer.join(" "));

 

💡시간복잡도

 

💡 틀린 이유 & 틀린 부분 수정

중복 탐색을 고려하지 않아서 틀림

 

💡 다른 풀이 or 기억할정보

queue.shift() 
 : 배열의 맨 앞에 값을 제거