BOJ/백트래킹 || 재귀
[C++] BOJ 1941 / 백트래킹 (소문난 칠공주, next_permutation 사용)
문제 분석 https://www.acmicpc.net/problem/1941 25명의 여학생들 중에 문제 조건에 맞는 인접한 그룹의 경우의 수를 출력하는 문제이다. 주어진 조건은 1. 여학생 수가 7명이어야 한다 2. 7명은 가로나 세로로 인접해 있어야 한다. 3. 7명 전부 이다솜파 일 필요는 없다. 4. 최소 이다솜파가 4명 이상은 반드시 포함되어야 한다. 해결 방법 1. 총 25명 학생 중에서 7명을 뽑아야 한다. (1번 조건 충족 시키기) - next_permutation 사용 2. 7명 중에 이다솜파가 4명 이상 있는지 확인한다. (4번 조건 충족 시키기) 3. 7명이 서로 인접해 있는지 확인한다. (2번 조건 충족 시키기) - BFS 사용 코드 #include #include #include ..
[C++] BOJ 9663 / 백트래킹 (N-Queen, 2차원 배열 속 대각선 계산)
문제 분석 https://www.acmicpc.net/problem/9663 크기가 N X N 인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 방법의 수를 출력하는 문제이다. 체스 말에서의 퀸은 대각선을 포함한 상하좌우로 여러 칸 이동 가능하다. 해결 방법 퀸을 행 별로 하나 씩 배치하면서, 만나지 않는 경우를 전부 찾아야 하므로 백트래킹을 사용해야한다. 행 별로 하나 씩 두기 때문에, 같은 행에 있는지는 체크 하지 않아도 되지만, 같은 열에 있는지와 우측 대각선 좌측 대각선에 있는지 체크하기 위해 배열을 3개 사용해야한다. 같은 대각선에 있음을 확인하는 방법은, x+y가 같으면 좌측하단에서 우측상단을 잇는 대각선에 위치해있다. 반대로 좌측상단에서 우측하단을 잇는 대각선은 x-y가 같은지 확인하면 ..
[C++] BOJ 15649 / 백트래킹 (M과 N(1), 백트래킹 첫 도전)
문제 분석 https://www.acmicpc.net/problem/15649 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력하는 문제이다. 해결 방법 비어있는 리스트에 가능한 숫자를 넣어가며, 리스트의 사이즈가 M이 됐을 때를 base case로 설정하여 구현한다. 중복 없이 고른다는 조건이 있기 때문에, 이미 리스트에 포함되어 있는 숫자인지 체크하기 위한 배열을 선언해야한다. 코드 #include using namespace std; int n,m; int arr[10]; bool choice[10]; void pick(int k) { if(k==m) { for(int i=0;i
[C++] BOJ 2447 / 재귀 (별 찍기10 / Divide and Conquer)
문제 분석 https://www.acmicpc.net/problem/2447 별 찍기 문제이지만, 규칙이 정해져 있으므로 재귀로 구현해야 한다. 해결 방법 N에 따라서 균등하게 9등분이 가능하다. 9등분을 하며 재귀호출을 하고, 5번 째 조각일 경우에 호출을 건너뛰면 된다. base case는 n이 1일 때, 즉 더이상 나눌 수 없을 때 이다. 코드 #include #include using namespace std; char board[2188][2188]; // 3^7 == 2187 void func(int x, int y, int n) { if(n == 1) { board[x][y] = '*'; } else { int div = n/3; for(int i=0;i n; for(int i=0;i