백트래킹

[python] 조합을 DFS로 구하기

항상 combinations로만 조합을 구했는데 이제는 한번 정리를 해야할것 같아서 오랜만에 글을 쓴다. 이문제는 백준 15650번으로 조합을 구하면 되는 문제이다. 사실 라이브러리를 사용한다면 상당히 쉬운 문제이다. from itertools import combinations N, M = map(int, input().split()) for com in list(combinations([i for i in range(1, N+1)], M)): print(" ".join(map(str, com))) 그러나 이렇게 푸는게 습관이 되어 나중에 백트래킹 문제가 어렵게 느껴졌고 기초적인 문제를 코테에서 틀리는 상황이 발생했다. 따라서 이걸 DFS로 풀어보자. 4에서 3개를 뽑는 경우는 [1,2,3],[1,2,..

백준 9663 풀이 (백트래킹, 재귀함수)

사실 어제 풀다가 안풀려서 포기했다. 어제 짠 코드는 모든 경우를 다 확인하다보니 시간도 오래걸리고, 무엇보다 중복이 생겼다. 그래서 그냥 시원하게 던져버리고 오늘 다시 풀어보았다. 오늘은 접근을 달리했다. N * N개의 판에서 퀸이 4개가 들어가야한다고 하는데 이는 결국 각 행마다 퀸이 딱 하나씩 들어가야한다는 소리다. 즉, 무조건 배열이 [[0,?], [1,?], [2,?], [3,?] ......[n-1,?]] 이런 방식이면 되는거다. 따라서 이를 토대로 코드를 짰다. N = int(input()) sum = 0 def queen(tlist,n): global N global sum if len(tlist) == N: sum+=1 return for i in range(N): check = 0 fo..

백준 15649 풀이 (재귀함수, 백트래킹)

음 백트래킹이 먼지 몰랐다. 그래서 여기저기 기웃거려본 결과 트리를 만들때 불필요한걸 쳐내면서 트리를 만드는거 같다. 물론 이 문제에 백트래킹을 어떻게 적용해야하는지 전혀 이해못했다. 그냥 재귀함수로 적용해서 풀어보자! 라는 마인드로 풀었는데 어찌저찌 풀리긴 풀렸다. 순서는 다음과 같다. 1. 빈 리스트, n, m을 인자로 넣어준다. 2. for 을 이용하여 사용되지 않은 숫자를 리스트에 추가하며 재귀함수를 실행시킨다. 3. m을 하나씩 줄여서 m이 0이 되면 리스트에 저장된 값을 출력해준다. n,m = map(int,input().split()) Map=[i for i in range(1,n+1)] def back(tlist, n,m): if m == 0: for i in tlist: print(Map..