백트래킹

[백준 9663] N-Queen 문제 출처 : 링크 백트래킹을 활용하는 가장 유명한 백준 문제가 N-Queen이다. 체스에서 존재하는 '퀸'이 서로 공격할 수 없도록 체스판에 둘 수 있는 방법의 수를 구해야 한다. 퀸은 체스에서 가장 강력한 존재로, 자신이 위치한 곳에서 가로 줄, 세로 줄, 대각선을 모두 움직일 수 있다. N * N 체스판에서 퀸들이 서로 공격하지 못하는 위치를 찾는 것이 문제의 핵심이다. 체스판이라 2차원 배열로 접근해야 된다고 생각할 수 있지만, 이 문제는 1차원으로 해결이 가능하다.왜냐하면, 어차피 하나의 열에 퀸 하나를 두면, 해당 열에는 추가로 더 놓을 수 없기 때문이다.(즉, 하나의 열마다 하나의 퀸만 놓으면 됨) 우선 Queen에 대한 Class를 만들자 123456789c..

[알고리즘] 백트래킹(Backtracking) [알고리즘] 백트래킹(Backtracking) 백트래킹이란?모든 경우의 수를 검색하는 알고리즘'특정조건'을 만족하는 모든 경우의 수를 찾고 싶을 때 유용DFS(깊이 우선 탐색)을 기반으로 하는 알고리즘 후보해 집합에서 최적해 집합을 찾아내는 문제에 적용 가능!후보해 : 정답이 될 가능성이 있는 모든 조합최적해 : 문제의 답으로 기준을 만족하는 해 DFS는 Brute Force 알고리즘으로, 재귀함수를 통해 그냥 모두 다 검사해서 찾음 DFS와 백트래킹의 차이점은 '가지치기'가지치기를 이용하기 때문에 DFS처럼 모든 경우의 수를 확인하는 알고리즘은 아님! 가지치기는 어렵게 생각하지말고 반복문에서 break나 return에 해당한다고 생각하자 백트래킹 대표 문제..