반응형 dfs2 [ 백준 ] 10451 번 순열 사이클 파이썬python 풀이 // 문제 요약 1부터 N 까지 정수로 만들 수 있는 순열의 한 가지 경우가 주어질 경우 1부터 N 까지 오름차순으로 정렬한 순열과 1대 1 대응 하여 만들 수 있는 그래프에서 순환 구조는 몇개가 생기는지 리턴하는 함수를 만들어라. //사고 문제를 이해하는게 어려운 문제다. 문제의 참고자료를 보면 그림이 아주 잘 나와있는데 이런 행렬이 주어지면 첫번째 행이 from 두번째 행이 to 가 되는 그래프를 그릴 수 있다. 그려본다면 이런식이다. 모두 같은 숫자로 이루어진 순열이므로 뻗어나가고 끝나는 가지는 존재하지 않게 되고 순환구조가 발생하게 된다. 파이썬에서는 dfs를 이용하면 순환구조를 간단하게 찾을 수 있는 테크닉이 존재하는데 바로 파이썬의 set() 를 이용한 진행경로 추적이다. dfs의 경우 깊이를.. 2021. 7. 29. [ 프로그래머스 ] N-Queen 파이썬python 풀이 // 문제 요약 자연수 n 이 주어질때 n x n 의 채스판에서 n개의 퀸이 서로를 공격할 수 없도록 위치시킬 수 있는 경우의 수를 모두 구해라. // 풀이 dfs 중에서도 백트래킹 문제다. 사실은 "모든 경우의 수" 문제이므로 브루트 포스이긴 한데 이후의 사건이 이전의 사건에 종속적이므로 조건문을 통해 가지를 치는 것이 가능하다. 이런 문제가 가장 어려운 부분은 여러 겹의 for문으로 브루트 포스로 설계할 것인가? 수학적 접근으로 n에 대한 규칙을 찾을 것인가? 재귀 함수를 통해 백트래킹을 할 것인가? 이 선택을 순간적으로 하기 어렵다는 것이다. n이 작으니 브루트 포스도 그럴싸해 보이고 그림을 그려보면 묘하게 페턴도 있어 보이며 백트래킹을 잘 쓰면 굉장히 섹시한 답을 제출할 수도 있어 보인다. 이럴 .. 2021. 6. 7. 이전 1 다음 반응형
