백준 1759 - 암호 만들기 (백트래킹) JS

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

해당 문제는 몇 가지 알파벳을 제시한 후, 특정 조건(모음 1개 이상, 자음 2개 이상)을 만족하는 암호를 출력하는 문제다.

 

나는 산출할 수 있는 모든 조합을 만들 수 있는 백트래킹 로직과, 만들어진 조합을 검증하는 검증 로직 두 가지를 구현하여 문제를 해결하였다.

 

const fs = require('fs')
const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt")
  .toString().trim().split('\n')

// 검증 로직
const verify = (arr) => {
  // 모음 배열
  const vowels = ['a','e','i','o','u']
  const table = {}
  arr.forEach((el)=> {
  	// 모음일 경우, table['vowels'] / 자음일 경우 table['cons']에 갯수 추가
    vowels.indexOf(el) !== -1 
    ? table['vowels'] = (table['vowels'] || 0) + 1 
    : table['cons'] = (table['cons'] || 0) + 1
  })
  // 자음, 모음 갯수 검증 리턴
  return table['vowels'] > 0 && table['cons'] > 1
}

function solution(data) {
  const [[N,M], temp] = data.map(el => el.split(' '))
  // 알파벳 순 정렬
  const chars = temp.sort()

  // 결괏값을 담는 배열
  const result = []
  // 백트래킹 시 산출되는 문자들을 저장하기 위한 임시 배열
  const storage = []
  // 중복 사용을 막기 위한 배열
  const visited = Array.from({length : M}, ()=> false)

  // 백트래킹 로직
  const backTracking = (n) => {
  // 길이 만족 시
    if(storage.length === +N) {
    // 검증에 통과하면 result 배열에 추가
      if(verify(storage)) result.push(storage.join(''))
      return
    }

    for(let i = n ; i < M ; i ++) {
    // 방문(중복)한 곳이라면 패스
      if(visited[i]) continue
      // 방문 처리 및 storage 배열에 해당 값 추가
      visited[i] = true
      storage.push(chars[i])
      // 재귀적으로 backTracking 함수 실행
      backTracking(i)
      // 방문 취소 및 storage 배열에 해당 값 제거
      storage.pop()
      visited[i] = false
    }
  }
  // 정렬된 변수인 chars의 0번 인덱스에서 시작하므로 초기값은 0
  backTracking(0)

  console.log(result.join('\n'))
}

solution(input)

 

예전, 백준에서 순열에 대한 문제 풀이 방식을 보고 응용해서 해결했다. (처음에는 개념 자체가 이해가 안되서 vscode의 디버깅을 활용하며 이해했었더랬다.)