백준 js, Python - N과M(5)

 

백 트래킹 알고리즘 카테고리에서 N과 M 시리즈 문제를 풀고있다. 대표적인 백 트래킹 문제로 (1)~(5)까지 풀어보면서 감을 익히고 있다. 

 

Js와 Python 두 가지 언어를 이용하여 문제를 풀어보고 있는데 두 언어가 문법이 비슷해서 그런지 파이썬을 시작한지 얼마 되지 않았지만 금방 익숙해진것 같다 ㅎㅎ.. 하지만 아직 멀었다 생각하고 푸는 양을 일단 늘려보자

 

<문제>

 

<문제 핵심>

 

1.  위에서 말했듯이 백트래킹을 사용해야 하는 문제! 자바스크립트, 파이썬 기반으로 문제를 풀 때 공통적인 부분이 존재한다. 일단 재귀를 탈출하기 위한 조건문이 존재하고 반복문을 통해 해당 요소에 방문했는지를 판단하게 된다. 방문을 안했다면 seq 배열과 result 배열에 방문을 안한 요소를 넣어준다.

 

차이점으로 파이썬 기반으로 문제를 풀 때는 visitied 배열을 만들지 않았다. result 배열에서 array 배열의 요소가 없다면 이는 곧 방문을 안한 것을 의미하므로 없을 경우 result배열에 append 해주는 방법으로 구현했다.(밑에 첨부된 코드 참고)

 

 

2. 입력값의 두번째 줄을 보면 4 5 2 처럼 정렬이 안 되어있는 것을 볼수있다. 출력값을 볼 때 정렬을 기반으로 백 트래킹이 적용되기에 먼저 오름차순 정렬을 해줘야 한다.

 

결론적으로 자바스크립트 에서는 sort() , 파이썬에서는 sorted()를 적용하였다.

 

 

 

오름차순 정렬 확인

 

 

<전체 코드 - Js>

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

const [N, M] = input.shift().split(" ").map(Number);
const array = input[0]
  .split(" ")
  .map(Number)
  .sort((a, b) => a - b);
let result = "";

function solution(n, m) {
  const seq = [...Array(m)].fill(0); //[0]
  const visited = [...Array(n)].fill(false); //[false, false, false, false]
  const dfs = (k, start) => {
    if (k === m) {
      const arr = [];
      for (let i = 0; i < m; i++) {
        arr.push(seq[i]);
      }
      return (result += `${arr.join(" ")}\n`);
    }

    for (let i = 0; i < array.length; i++) {
      if (!visited[i]) {
        seq[k] = array[i];
        visited[i] = true;
        dfs(k + 1, array[i + 1]);
        visited[i] = false;
      }
    }
  };

  dfs(0, array[0]); //0부터 호출해야함
  return result;
}

console.log(solution(N, M));

 

<전체 코드 - Python>

def solve(N, K, array):
  
    result = []

    def dfs():
        if(len(result) == K) :
            print(' '.join(map(str, result)))
            return
        
        for i in range(N):#result에 array의 요소가 없다면 넣어라
            if array[i] not in result:
                result.append(array[i])
                dfs()
                result.pop()

    dfs()

# 메인 함수
if __name__ == "__main__":
    N, K = map(int, input().split())
    array = sorted(list(map(int, input().split())))
    
    solve(N, K, array)

 

 

확실히 유형별로 계속 푸니까 공통적으로 사용되는 코드 형태를 발견할 수 있었다. 물론 아직 어렵지만 계속 유형별로 풀어보면서 부족한 부분을 보완해야겠다.

 

<알고리즘 공부 레포지토리>

https://github.com/Jayjunyoung/JS_Python_Algorithm

GitHub - Jayjunyoung/JS_Python_Algorithm