백준에서 nodeJS 사용하기 (#05): 백트랙킹 - DFS & BFS #1260번 #15652번 #9663번

Kyle Lee·2022년 1월 20일
0
post-thumbnail

1. 서론

알고리즘 문제풀이를 하다보면 두 부류로 나뉘곤 하는데, 전체 경우의 수를 확인해야하는 문제와 특정 값을 찾는 문제가 있습니다.

탐색 vs 검색

전자를 탐색이라고 하고 후자를 검색이라 합니다.
즉, 탐색은 가장 좋은 조건이나 특정 조건을 만족하는 경우의 수 등 자신이 찾는 것이 무엇인지 명확하지 않을 때 사용하는 방식이고 검색자신이 찾는 것이 명확하고 무엇인지 아는 경우에 사용하는 방식입니다.

백트랙킹

백트랙킹은 이 중 전체 경우의 수를 확인해야할 때 사용하는 트리기반의 탐색 알고리즘입니다.
백트랙킹에는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)으로 나뉘는데, DFS는 스택(LIFO)을 사용하고 BFS는 큐(FIFO)를 사용합니다. 그렇기 때문에 모든 경우의 수를 검사해야한다면 DFS를 사용하는 것이 좋고, 최단거리나 분기점 도중에 해답이 나오는 경우에는 BFS를 사용하는 것이 일반적으로 좋습니다.

2. DFS & BFS

DFS - 완전 탐색

DFS는 상태공간(모든 경우의 수)을 나타낸 트리에서 한 쪽 방향으로만 내려가는 방식이다. 바닥에 도달할 때까지 내려간 다음, 다시 트리 위로 올라오면서 다음 분기점에서 다른 방향으로 가는 방식입니다. 이를 목표 값이 나올 때까지 반복합니다.

스택형 방식이지만 일반적으로는 재귀함수로 구현해서 사용하곤 합니다.

// Pseudo code example
// N은 스택의 깊이
function dfs(idx){
  // terminal condition
  if(idx === N){
    ```
      탐색 종료 코드
    ```
    return;
  } else {
    for(let i = 0; i < Stack.length; i++){
      // stack in
      ```
        스택 처리 코드
          ex) - 둘은 한쌍
          DFSStack.push(node);
  		  visited[node] = true;
      ```
      // 재귀함수
      dfs(idx + 1);
      // stack out
      ```
        스택 처리 코드
      ```
    }
  }
}

BFS - 단순 검색

BFS는 최초 루트 노드에 인접한 모든 노드를 먼저 확인하고 그 다음 단계로 넘어가는 방식입니다.

무한루프(while True)에 빠질 위험이 있기 때문에 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 합니다.

BFS는 재귀적으로 동작하지 않고 선입선출(FIFO) 원칙으로 탐색하기 때문에 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 큐를 사용합니다.

2-1. 문제 1260번: DFS와 BFS

dfs(v: 현재 노드){
	if(v - 방문 확인) return;
    
    v 방문한 사실을 저장;
    결과 변수 배열 맨 뒤에 v값 삽입;
    
    v와 인접한 정점들의 배열의 첫 번째 정점부터 순서대로
    방문하지 않은 정점에 대해 dfs(정점) 호출;
}
bfs(v - 루트 노드){
	방문할 정점 배열 선언 = [v];
    while(방문할 정점 배열.length !== 0){
    	v = 방문할 정점 배열 shift;
        if(v - 방문 확인){
        	continue;
        }
        
        v 방문 저장 = true;
        결과 배열에 v값 push;
        v와 인접한 정점 배열의 첫 번째 정점부터
        방문하지 않은 정점을 방문할 정점 배열의 끝에 삽입;
    }
}
let [N, ...input ] = require('fs').readFileSync('test.txt').toString().trim().split("\n");
let [n, m, k] = N.split(" ").map(Number);

// construct graph.
let graph = [...Array(+n)].map(()=>[]);
let DFSvisited = new Array(n+1).fill(false);
let BFSvisited = new Array(n+1).fill(false);
let DFSStack = [];
let BFSQueue = [];

for(let i = 1; i< n+1; i++){
  input.forEach(e => {
    let ab = e.split(" ").map(Number);
    if(ab.includes(i)){
      ab[0] == i ? graph[i-1].push(ab[1]) : graph[i-1].push(ab[0])
    }
  });
}

graph.forEach(e => {
  e.sort((a, b)=> a- b);
})

// dfs - stack.
const dfs = (node) => {
  if(DFSvisited[node]) return;

  DFSStack.push(node);
  DFSvisited[node] = true;

  graph[node-1].forEach(v=>{
      if(!DFSvisited[v]){
          dfs(v);
      }
  })
}


// bfs - queue.
const bfs = (node) => {
  let queue = [node];

  while(queue.length !== 0){
    let q = queue.shift();

    if(BFSvisited[q]){
      continue;
    }

    BFSQueue.push(q);
    BFSvisited[q] = true;

    graph[q-1].forEach(v=>{
      if(!BFSvisited[v]){
        queue.push(v);
      }
    });
  }
}

const solution = () => {
  dfs(k);
  bfs(k);
  console.log(DFSStack.join(" "));
  console.log(BFSQueue.join(" "));
}

solution();

3. 문제 15652번 : N과 M (4)


해당 문제는 Permutation을 출력하지만 같은 수의 중복을 허용하고 있기 때문에 사실상 Combination을 출력하는 문제입니다. nCm을 출력하기 위해서 위의 DFS 예제 형식의 코드를 사용하면 대략 이런 식의 코드를 만들 수 있습니다.

let [N, M] = require("fs").readFileSync("/dev/stdin").toString().trim().split(" ").map((a) => +a);

let ANSWER = "";
let prefix = [];
function combination(n, count) {
  if (prefix.length == M) {
    ANSWER += prefix.join(" ") + "\n";
    return;
  }
  // 1 ~ N 까지의 자연수를 출력하기 위해 1부터 시작
  for (let i = count; i < n + 1; i++) {
    // prefix stack in till it reaches terminal node
    prefix.push(i);
    // 재귀함수
    combination(n, i);
    // when it reached terminal node, then prefix stack out
    prefix.pop();
  }
}

combination(N, 1);
console.log(ANSWER);

좀 더 내부 구조를 이해하기 쉽게 예시를 활용하면,
let [N, M] = [4, 2]의 실행 결과는 다음과 같습니다.

4. 문제 9663번 : N-Queens

해당 문제는 백트랙킹의 대표적인 문제로 N개의 퀸을 N*N 크기의 체스판에 배치하는 경우의 수를 확인하는 문제입니다.

보통의 경우 체스판과 같은 예시에서는 2차원 배열을 생성하여 문제를 풀지만 이 문제의 경우에는 퀸의 특성상 한 가로줄과 세로줄에는 동시에 같은 퀸이 존재할 수 없기 때문에 체스판을 1파원 배열로 압축할 수 있습니다.

배열의 인덱스를 column으로, 배열의 값을 row로 생각하면 1차원 배열만으로 퀸의 배치를 표현할 수 있습니다.

이 문제의 포인트는 대각선 줄의 퀸을 어떻게 제거하는 것이냐인데, 이를 기존 배열에 배치된 퀸의 위치와 각 배열의 인덱스와 값의 절대값을 통해 대각선 배치를 방치할 수 있었습니다.

  • 예시 코드 : Math.abs(array[x] - array[i]) == x - i

처음의 접근은 다음 배치때 이를 만족하는 경우의 수를 확인하는 방식으로 접근해서 많이 어려웠는데 반대로 가능한 배치를 기존 배열로부터 확인하는 방법이 훨씬 문제를 쉽게 해결하는 열쇠가 되었습니다.

let N = Number(require("fs").readFileSync("test.txt").toString().trim());

let array = new Array(N + 1).fill(0);
let answer = "";
let count = 0;

function dfs(x) {
  // 이번 문제의 stack out은 checker를 통해 구현되었다. 
  // 만약 checker를 통과하지 못한다면 자연스럽게 다음 노드로 넘어가지 못하고 패스된다.
  if (checker(x)) {
    if (x == N) {
      count++;
      // 문제 자체는 개수만 요구하기 때문에 하단의 join 구문은 필요가 없다.
      let coiped = [...array];
      answer += coiped.join(" ") + "\n";
      return;
    }
    // 1~N까지의 체스판을 보여주기 위해 1부터 시작
    // 또한 첫번째 노드가 checker를 통과하기 위해서는 배열의 첫번째 값을 의도적으로 배제해야한다.
    for (let i = 1; i < N + 1; i++) {
      array[x + 1] = i;
      dfs(x + 1);
    }
  }
}

function checker(x) {
  for (let i = 1; i < x; i++) {
    if (array[x] == array[i] || Math.abs(array[x] - array[i]) == x - i) {
    return false;
    }
  }
  return true;
}

dfs(0);
console.log(answer);

참고문헌

https://namu.wiki/w/%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9
https://kscodebase.tistory.com/518

profile
필요에 의한 개발

0개의 댓글