Koala - 7기/기초 알고리즘 스터디
[백준/C++] 9663 N-Queen
5호선파브르구너
2022. 8. 27. 21:57
https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
소스코드
문제풀이
백트래킹 문제의 대표적인 문제라고 한다. 혼자 그림을 그려서 생각해보면 아 이런식으로 풀어야겠구나 라는 생각은 금방 들지만 재귀를 이용해서 구현하기 어려웠다.(백트래킹 문제는 많이 풀어보는 수밖에 없는거같다) 한 곳에 뒀을 때 퀸을 둘 수 있는 곳에만 두는 식으로 점점 숫자를 늘려가며, 어느 곳에도 퀸을 둘 수 없으면 이 곳에 두면 안된다고 체크하고 되돌려놓는 형태로 풀면 된다. (N과 M 풀때처럼 푸는데, N과 M은 기존의 코드를 바꿔가면서 풀다 보니까 N-Queen은 풀기가 어려웠다. 사실, 백트래킹 감을 못 잡았는데 어거지로 푼거같다.)