[STUDY] 백트래킹 알고리즘 문제풀이 4 (BackTracking Algorithm) 231019

1. N-Queen

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

강의에서 제시한 문제 해결 아이디어

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 모든 수열을 계산
• 모든 순열의 수를 고려하기 위해 재귀 함수(백트래킹)를 사용할 수 있다.
• 하나의 순열을 트리(tree)에서 리프 노드까지의 경로로 생각할 수 있다.
  -> 이때, M개의 원소를 뽑는 순열을 고려하는 것이므로, 깊이(depth)는 M과 같다. -원소를 중복하여 선택하지 않으므로, 방문처리(visited) 배열을 사용한다.
  -> 한 번 선택된 원소는 다음 재귀 함수에서 다시 선택되지 않는다.

제출 답안

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let n = Number(input[0]); // 전체 map의 크기
let queens = []; // 현재 체스판에 놓인 퀸(queen)의 위치 정보들

function possible(x, y) {
  // (x, y) 위치에 퀸을 놓을 수 있는지 확인
  for (let [a, b] of queens) {
    // 현재까지 놓았던 모든 queen의 위치를 하나씩 확인하며
    if (a == x || b == y) return false; // 행이나 열이 같다면 X
    if (Math.abs(a - x) == Math.abs(b - y)) return false; // 대각선 위치한 경우 X
  }
  return true;
}

let cnt = 0;
function dfs(row) {
  if (row == n) cnt += 1; // queen을 N개 배치할 수 있는 경우 카운트
  for (let i = 0; i < n; i++) {
    // 현재 행(row)에 존재하는 열을 하나씩 확인하며
    if (!possible(row, i)) continue; // 현재 위치에 놓을 수 없다면 무시
    queens.push([row, i]); // 현재 위치에 퀸 놓기
    dfs(row + 1); // 재귀함수 호출
    queens.pop(); // 현재 위치에서 퀸 제거
  }
}
dfs(0);
console.log(cnt);

정답 예시

제출 답안과 동일

2. 알파벳

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

정답 예시

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let [r, c] = input[0].split(" ").map(Number);
let arr = []; // 순열을 계산하고자 하는 원소가 담긴 배열
for (let i = 1; i <= r; i++) arr.push(input[i]);

let dx = [-1, 1, 0, 0]; // 상하좌우 방향
let dy = [0, 0, -1, 1];

let visited = new Set(); // 방문한 적 있는 알파벳 집합
let maxDepth = 0; // 최대 깊이

function dfs(depth, x, y) {
  maxDepth = Math.max(maxDepth, depth); //최대 깊이 계산
  for (let i = 0; i < 4; i++) {
    let nx = x + dx[i];
    let ny = y + dy[i];
    if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue; // 맵을 벗어나면 무시
    if (visited.has(arr[nx][ny])) continue;
    visited.add(arr[nx][ny]); // 방문 처리
    dfs(arr, depth + 1); // 재귀 함수 호출
    visited.delete(arr[nx][ny]); // 방문처리 해제
  }
}
visited.add(arr[0][0]); // 왼쪽 위에서 출발
dfc(1, 0, 0);
console.log(maxDepth);

3. 부등호

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

강의에서 제시한 문제 해결 아이디어

• 총 10개의 숫자 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 중에서 중복 없이 모든 순열을 선택 한다.
• 선택한 뒤에 K 개의 부등호에 대한 순서를 만족하는지 확인한다.
• K는 최대 9까지 입력될 수 있다.

정답 예시

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let k = Number(input[0]);
let arr = input[1].split(' ');
let visited = new Array(10).fill(false);
let result = [];
let current = "";
let first = "";

dfs(0);
console.log(current + "\n" + first) // 마지막에 남은 current 값은 [가장 큰 문자열]


function dfs(depth) {
  if (depth == k+1) { //각 순열에 대한 처리
   let check = true; // 부등식을 만족하는지 확인
    for (let i = 0; i < k; i++) {
      if (arr[i] =="<") {
        if(result[i] > result[i+1]) check = false; // 부등식을 만족하지 않음
      }
      else if (arr[i] == '>') {
        if(result[i] < result[i+1]) check = false; // 부등식을 만족하지 않음
      }
    }
    if (check) { // 부등식을 만족하는 경우에
      current = "";
      for (let x of result) current += x + "";
      if ( first == "") first = current; // 첫째 문자열은 [가장 작은 수]
    }
    return;
     }
     for (let i = 0; i < 10; i++;) { // 0부터 9까지의 숫자를 하나씩 고르는 순열(백트래킹)
   if (visited[i]) continue; // 이미 고른 숫자라면 무시하도록
    visited[i] = true; // 현재 선택한 숫자 방문 처리
    result.push(i);
    dfs(depth + 1); // 재귀 함수 호출
    visited[i] = false; //현재 선택한 숫자 방문 처리 취소
    result.pop();
  }
}