문제
https://www.acmicpc.net/problem/9663
[ 문제 조건 ]
- 1 ≤ N < 15
- 출력 : 서로 공격할 수 없게 놓는 경우의 수
- 백트래킹 문제 → 개념을 알고 있어야 함
[ 해결순서 ]
- 체스판에 퀸을 놓기위한 조건은 퀸의 가로, 세로, 대각선에 위치한 곳에 두면 안된다.
- 백 트래킹 문제에선 퀸을 놓을 때 직전의 열에 두지 않는다고 한다. ( 중복제거를 위해 )
- 하나의 행에 하나의 퀸만 놓을 수 있다.
- 그렇다면 N * N개의 경우의 수가 존재 할 텐데 이 중에서 서로 공격하지 않게 놓는 경우의 수를 구해야한다.
- nqeen()은 퀸을 오른쪽 행으로 하나씩 옮기면서 경우의 수를 확인하고
- check()로 행은 비교할 필요가 없고 (3번참고) 같은 열인지, 대각선상에 있는지 비교한다.
- nqeen()에서 퀸이 끝 행까지 도달했다면 경우의 수(count)를 하나 추가해준다.
- 이를 재귀적으로 반복해서 값을 구한다.
[ 예제 직접구현 ]
✏️한줄평
: 백 트래킹이 무엇인지 개념을 파악할 수 있었다. 처음 접한 개념이라 낯설게 느껴져 시간소요를 많이 했지만 다시 복습하거나 다른 비슷한 유형 풀면서 익숙해져야겠다.
코드
'알고리즘' 카테고리의 다른 글
[Python] 백준 1932 : 정수 삼각형 (0) | 2021.08.23 |
---|---|
[Python] 백준 1946 : 신입사원 (0) | 2021.08.23 |
[Python] 백준 2468번 - 안전 영역 (0) | 2021.08.09 |
[Python] map 함수로 2차원배열의 최대값 구하기 (0) | 2021.08.09 |
[Python] 백준 9020번 - 골드바흐의 추측 (0) | 2021.08.06 |