백트래킹

(C++) 백준 9663번 - N-Queen

문제 링크 : https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 백트래킹을 활용하여 풀이하였다. Queen은 같은 행이나 열, 같은 대각선 상에 존재하면 서로를 잡을 수 있다는 점을 알아야 한다. 그렇기에 한 행에 놓으면 같은 행의 다른 칸에 놓을 수 없음을 이용하여 한 행에 Queen을 하나씩만 두고, 열과 대각선 상만 피해서 Queen을 놓게 구현하면 된다. #include using namespace std; int n; int isUsedcol[15..

(C++) 백준 15649번 - N과 M (1)

문제 링크 : https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 백트래킹을 사용한 풀이이다. 이미 특정 숫자가 배열에 들어가 있는지 arr을 순회하면서 확인하고, 들어있지 않은 숫자들만 배열에 삽입한다. 사이즈가 m이 되는 순간 지금까지 배열에 저장해 놓은 숫자들을 출력한다. #include using namespace std; int n, m; int arr[8]; void nNm(int num, int idx){ for(int x = ..