Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
반응형
문제
https://www.acmicpc.net/problem/9663
9663번: N-Queen
N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
www.acmicpc.net
풀이
bool board[14][14] : 퀸을 놓기가 가능하면 true로 저장해 둠.
void BanBoard(int r,int c) : r과 c 위치에 퀸을 둘 경우 양대각과 가로 세로의 board를 false로 변경
voidDfs(int column): column이 N이상일 경우만 cnt를 +1하고 나머지에서는 퀸을 하나씩 두며 Dfs 재귀 호출
board_copy를 선언해 이전의 board의 값을 저장해 두고 column의 row값을 for문으로 돈다.
만약 퀸을 두는 것이 가능하면 BanBoard를 호출 후 Dfs(column+1)를 재귀 호출해 다음 column에서 가능한 수를 찾는다.
후출 후 돌아온다면 이전의 board값으로 복구시키기 위해 copy_board값을 다시 넣어준다.
소스코드
복기
if(column >= N) 부분에서 N-1과 비교해 한참을 헤맸다..
반응형
'알고리즘 공부 > 백준' 카테고리의 다른 글
| [백준] No. 1038 - 감소하는 수 (C++) (0) | 2020.10.24 |
|---|---|
| [백준] No. 14500 - 테트로미노 (C++) (0) | 2020.10.19 |
| [백준] NO.12100 - 2048 (Easy)(C++) (0) | 2020.10.19 |
| [백준]No.2580 - 스도쿠 (C++) (0) | 2020.08.29 |
| [백준] No.2573 - 빙산 (C++) (369) | 2020.08.14 |
댓글