Devjo의 코딩

N-Queen 10 초 128 MB 56575 28380 18609 49.681% 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 풀이 원리나 풀이 부분은 이미 충분히 다뤄왔기 때문에 상세히 다루지는 않겠습니다.. 백트래킹(Backtracking)의 개념과 DFS로의 확장, N-Queen 백트래킹 해를 찾는 중에 현재 선택한 루트(노드)가 해와 관련이 없다는 것을 알아차리면 중단하고(가지치기) 이전 단계로 돌아가 다른 루트를 탐색한다 해가 될 ..

N-Queen 10 초 128 MB 50440 25920 16972 50.773% 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 풀이 백트래킹의 대표 문제 중 하나라고 한다. N-Queen에 규칙에 의해 NxN 체스판에 N개의 퀸을 놓기 위해서는 각 줄에 하나씩 퀸을 놓아야만 한다. 즉 첫째줄이든, 둘째줄이든 퀸은 무조건 존재한다는 뜻이다. 이 규칙에 의해 첫째줄에 퀸은 무조건 놓일 수 밖에 없으므로 첫째줄(1행)에 퀸이 어느 자리(열)에 오..