백 트래킹 단골 문제다. 퀸이 갈 수 있는 좌표를 잘 표시하는게 관건인데, 현재 퀸의 좌표를 (x, y) 라고 하자.
그럼 현재 좌표에서 아래 대각선에 퀸이 존재하는지 알아보려면 x+y가 같으면 된다. (기울기가 -1)
그럼 반대로 위 대각선에 퀸이 존재하는지 알아보려면 x-y가 같으면 된다. (기울기가 1)
이런식으로 위 대각선, 아래 대각선, 행에 대한 bool 변수를 두고 체크해가면서 백트래킹 해주면 된다. 기본적인 백트래킹 방법은 좋은 강의가 많으니 그걸 참고하면 되겠다..
'PS > baekjoon' 카테고리의 다른 글
| [BOJ 10816] 숫자 카드 2 (2) | 2023.07.03 |
|---|---|
| [BOJ 1920] 수 찾기 (0) | 2023.07.03 |
| [BOJ 7562] 나이트의 이동 (0) | 2023.07.02 |
| [BOJ 17114] 하이퍼 토마토 (0) | 2023.07.02 |
| [BOJ] 7579 : 토마토 (3차원 BFS) (0) | 2023.07.02 |