1.N과 M
배열의 크기가 1~8로 작으므로 dfs를통해 해결한다
숫자를 넣을 배열 arr과 방문했는지 확인하는 visited배열을 선언한다
main 함수에서 n과m을 입력받은뒤 dfs(0)를 호출한다
dfs함수는 int cnt 를 인자로 받아 cnt가 m일때 즉 arr배열이 m자리 까지 완성되면 출력하고 void를 리턴한다
dfs(0)를 호출했을때 우리는 첫자리를 반복문을 통해 1부터 N까지 증가 시킬것이고 앞자리가 1일때 뒷자리는 2~n 또 그뒷자리도 탐색을 진행할것이고 이를 뒤에 전해주기위해 반복문 진입시 visited[i] 가 0인지 체크하고 시작한다 만약 1이라면 이미 앞에서 방문한경우이므로 건너뛴다
이런방식으로 마지막까지 수행해 문제를 해결할수있다.
2.N과 M
1번 문제의 cnt == m 즉 arr이 충족된상황에서 arr[i] > arr[i+1]을 통해 배열이 오름차순으로 되었는지 검사 하고 맞는경우에만 출력하는 방식으로 해결가능하다.
- N과 M
수가 중복되는경우도 출력하는것은 visted를 검사할필요없이 모두 출력해주면되므로 검사하는 부분을 빼주면 해결가능하다
- N_QUEEN
퀸을 놓는 문제이다 백트래킹으로 해결할때 board[15] 1차원 배열을 사용하고 가로칸에는 어차피 놓을수없으므로 각 인자는 1~n번째 줄에 몇번째 칸에 퀸을 놓았는지를 의미한다
백트래킹을 통해 모든칸을 검사할때 앞에서 틀렸다면 뒤에는 검사할필요가없다 이 검사가 문제의 핵심이다 퀸의 범위가 겹치지않기위해서는 같은 가로줄을 처리했으므로 같은 세로줄 혹은 대각선이 겹치면 안된다
check 함수를 구현하면
bool check_board(int num)
{
for (int i = 0; i < num; i++)
{
if (board[num] == board[i] || abs(board[num] - board[i]) == num - i)
return false;
}
return true;
}받은 인자 num은 현재 몇번째 줄까지 검사할것인지를 뜻한다 board배열은 0으로 초기화되어있거나 전에 검사한값이 들어가고 초기화되지않기때문에 꼭 몇번째 줄까지 검사할것인지 인자로 넘겨줘야한다 num을 인자로 받으면 첫번째 줄부터 num줄 전까지 검사한다.
board[num] == board[i]는 각 칸의 인자를 비교해서 같다면 같은 세로줄안에 있다는 의미가되므로 false를 리턴한다.
abs(board[num] - board[i]) == num - i 는 대각선의 겹치는 경우를 의미한다 절대값을 해준이유는 대각선 두개가있고 각각의 칸이 겹치는 칸은 내가 만약 num칸을 검사하고있다면 비교되는 i를 뺀값과 같다면 대각선 이 겹치는 경우를 뜻한다 예를들어 2번째 줄에 4번째칸에 퀸이 놓아져있고 5번째 줄을 검사한다면 board[num] =4 board[i] = 2 = abs(2) = 2 이므로 대각선에 걸리는 경우가된다.
이런식으로 백트래킹을 끝까지 마치고 queen부분에서 인자가 n과같이 들어온다면 n* n 을 만족하는 경우이므로 cnt++를 해주고 return 해준다.
- 연산자 끼워넣기
숫자와 operator의 숫자를 입력받은뒤
dfs를 통해 operator를 하나씩빼고 다음 dfs를 출력하는 방식으로 값을 구한뒤 가장 큰값일때 값을 교체한다.
