[Javascript] 백준 1260번 DFS와 BFS - node.js

이 글은 백준 1260번 DFS와 BFS를 풀이한다. Javascript를 이용해 알고리즘을 구현했다.

문제

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

입력

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

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

출력

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

예제 출력 1

1 2 4 3
1 2 3 4

풀이

접근

우선 입력으로 그래프를 만들고, dfs와 bfs 각각의 정의대로 알고리즘을 구현해 결과를 출력해야겠다고 생각했다. 

알고리즘

[1] 그래프 생성

간선이 연결하는 두 정점의 번호 M개를 이용해 그래프를 생성한다. 배열의 n번째 인덱스 요소가 n번 정점과 연결된 정점들로 이루어진 배열이 되도록 그래프 배열을 생성한다. 이때 연결된 정점들로 이루어진 배열의 요소들이 오름차순이 되도록 그래프를 만든다. 이는 정점 번호가 작은 것부터 방문해야 하는 문제의 조건을 만족하기 위함이다.

[2] DFS

깊이 우선 탐색 알고리즘에서는 인접한 정점을 발견한 후, 해당 정점을 방문하지 않은 상태라면 그 정점을 바로 방문한다. 이를 반복하다 방문하지 않은 인접 정점이 더이상 없다면 마지막에 따라왔던 간선을 따라 뒤로 돌아가고 이를 반복한다. 이는 재귀 호출을 이용해 구현하기 좋다.

다음은 dfs 함수의 수도 코드이다.

dfs(v: 현재 정점){
	if(v를 방문) 리턴;
    
    v 방문한 사실을 저장;
    결과 변수 배열 맨 뒤에 v값 삽입;
    
    v와 인접한 정점들의 배열의 첫 번째 정점부터 순서대로
    방문하지 않은 정점에 대해 dfs(정점) 호출;
}

[3] BFS

너비 우선 탐색 알고리즘에서는 현재 정점과 인접한 정점 중, 방문하지 않은 정점을 방문할 정점 배열에 저장한다. 그 후 배열에서 정점을 하나씩 뽑아 방문한다. 번호가 작은 정점부터 방문해야 하므로 방문할 정점 배열을 큐(queue)처럼 동작하게 한다.

다음은 bfs 함수의 수도 코드이다.

bfs(vStart: 처음에 방문해야 할 정점){
	방문할 정점 배열 = [vStart];
    while(방문할 정점 배열의 길이가 0이 될 때까지){
    	v = 방문할 정점 배열에서 첫 번째 요소를 pop;
        if(v 방문){
        	continue;
        }
        
        v 방문 사실 저장;
        결과 배열에 v값 push;
        v와 인접한 정점 배열의 첫 번째 정점부터
        방문하지 않은 정점을 방문할 정점 배열의 끝에 삽입;
    }
}

구현

코드 (아래 설명 있음)

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

const input = [];
let graph, visited, result;

const strToNumArr = (str) => str.split(" ").map((numString) => Number(numString));

require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", function (line) {
    input.push(line.trim());
  })
  .on("close", function () {
      const [N, M, V] = strToNumArr(input.shift());
      graph = [...Array(N+1)].map(()=>[]);
      visited = [...Array(N+1)].fill(false);
      let v1, v2;
      input.forEach((str)=>{
        [v1, v2] = strToNumArr(str);
        insertEdge(v1, v2);
        insertEdge(v2, v1);
      });

      result=[];
      dfs(V);
      console.log(result.join(" "));

      visited.fill(false);
      result=[];
      bfs(V);
      console.log(result.join(" "));
  });
  
  
const insertEdge = (vFront, vBack) => {
    let index;
    for(index=0; index<graph[vFront].length; index++){
        if(graph[vFront][index]<vBack){
            continue;
        }

        if(graph[vFront][index]===vBack){
            index=null;
        }
        break;
    }

    if(index!==null){
        graph[vFront].splice(index, 0, vBack);
    }
};

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

    visited[v]=true;
    result.push(v);
    graph[v].forEach((vertex)=>{
        if(!visited[vertex]){
            dfs(vertex);
        }
    });
};

const bfs = (vStart) => {
    const willVisit = [vStart];
    let v;
    while(willVisit.length!==0){
        v=willVisit.shift();
        if(visited[v]){
            continue;
        }

        visited[v]=true;
        result.push(v);
        graph[v].forEach((vertex)=>{
            if(!visited[vertex]){
                willVisit.push(vertex);
            }
        });
    }
}

설명

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

const input = [];
let graph, visited, result;

const strToNumArr = (str) => str.split(" ").map((numString) => Number(numString));

//입력 받고 결과 출력하는 부분
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", function (line) {
    input.push(line.trim());
  })
  .on("close", function () {
      const [N, M, V] = strToNumArr(input.shift());
      //그래프 배열의 요소 빈 배열로 초기화
      graph = [...Array(N+1)].map(()=>[]);
      //방문 사실 저장할 배열 초기화
      visited = [...Array(N+1)].fill(false);
      
      let v1, v2;
      //그래프 생성
      input.forEach((str)=>{
        [v1, v2] = strToNumArr(str);
        //graph[v1] 배열에 v2 오름차순 맞게 삽입
        insertEdge(v1, v2); 
        //graph[v2] 배열에 v1 오름차순 맞게 삽입
        insertEdge(v2, v1);
      });

      //결과 변수 초기화
      result=[];
      //깊이 우선 탐색
      dfs(V);
      //결과 출력
      console.log(result.join(" "));

      //방문 사실 저장하는 배열 초기화
      visited.fill(false);
      //결과 변수 초기화
      result=[];
      //너비 우선 탐색
      bfs(V);
      //결과 출력
      console.log(result.join(" "));
  });
  
//graph[vFront] 배열이 오름차순을 유지하도록 vBack을 적절한 위치에 삽입
const insertEdge = (vFront, vBack) => {
    let index;
    for(index=0; index<graph[vFront].length; index++){
        //인접한 정점 배열에서 vBack보다 크거나 같은 정점 찾을 때까지 continue
        if(graph[vFront][index]<vBack){
            continue;
        }
		
        //문제에서 두 정점 사이에 여러 개의 간선이 있을 수 있다고 했으므로
        //인접한 정점 배열에 이미 vBack 정점이 있다면 삽입 인덱스에 null 저장
        if(graph[vFront][index]===vBack){
            index=null;
        }
        break;
    }

	//삽입 인덱스가 null이 아니라면 vBack 삽입 인덱스에 삽입
    if(index!==null){
        graph[vFront].splice(index, 0, vBack);
    }
};

//깊이 우선 탐색, 현재 정점 매개변수로 받음
const dfs = (v) => {
	//이미 방문했으면 리턴
    if(visited[v]){
        return;
    }

	//방문 사실 저장
    visited[v]=true;
    //결과 변수에 정점 삽입
    result.push(v);
    //인접한 정점 배열을 차례로 돌며 방문하지 않은 정점 방문
    graph[v].forEach((vertex)=>{
        if(!visited[vertex]){
            dfs(vertex);
        }
    });
};

//너비 우선 탐색, 시작 정점 매개변수로 받음
const bfs = (vStart) => {
	//방문할 정점을 담는 배열
    const willVisit = [vStart];
    let v;
    //방문할 정점이 안 남을 때까지
    while(willVisit.length!==0){
    	//방문할 정점 배열의 첫 번째 원소 삭제 후 저장
        v=willVisit.shift();
        //이미 방문했으면 continue
        if(visited[v]){
            continue;
        }

		//방문 사실 저장
        visited[v]=true;
        //결과 변수에 정점 삽입
        result.push(v);
        //인접한 정점 배열을 차례로 돌며 방문하지 않은 정점을
        //방문할 정점 배열의 끝에 삽입
        graph[v].forEach((vertex)=>{
            if(!visited[vertex]){
                willVisit.push(vertex);
            }
        });
    }
}