걸음마부터 달리기
SWEA 2806 N-Queen 본문
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
import java.util.*;
import java.io.*;
class Main {
static int T;
static int N;
static int ans;
static int[][] visited;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
for (int l = 0; l < T; l++) {
N=Integer.parseInt(br.readLine());
ans=0;
for(int i=0; i<N; i++){
visited = new int[N][N];
fill(0,i);
fillDiagonal(0,i);
dfs(1);
}
System.out.printf("#%d %d\n",l+1,ans);
}
}
public static void dfs(int depth){
if(depth == N){
ans++;
return;
}
for(int i=0; i<N; i++){
if(check(depth,i)){
fill(depth,i);
fillDiagonal(depth,i);
dfs(depth+1);
erase(depth,i);
eraseDiagonal(depth,i);
}
}
}
public static boolean check(int a , int b){
if(visited[a][b]>0){
return false;
}
return true;
}
public static void fill(int a, int b){
for(int i=0; i<N; i++){
visited[a][i]++;
visited[i][b]++;
}
visited[a][b]--;
}
public static void fillDiagonal(int a, int b){
int d = 1;
while(d<N){
if(a-d>=0 && b-d>=0 ) visited[a-d][b-d]++;
if(a-d>=0 && b+d<N) visited[a-d][b+d]++;
if(a+d<N && b-d>=0) visited[a+d][b-d]++;
if(a+d<N && b+d<N) visited[a+d][b+d]++;
d++;
}
}
public static void erase(int a, int b){
for(int i=0; i<N; i++){
visited[a][i]--;
visited[i][b]--;
}
visited[a][b]++;
}
public static void eraseDiagonal(int a, int b){
int d = 1;
while(d<N){
if(a-d>=0 && b-d>=0 ) visited[a-d][b-d] --;
if(a-d>=0 && b+d<N) visited[a-d][b+d] --;
if(a+d<N && b-d>=0) visited[a+d][b-d] --;
if(a+d<N && b+d<N) visited[a+d][b+d] --;
d++;
}
}
}그냥 못풀었다. 거의 2시간 쏟아서 꾸역꾸역 혼자 힘으로 하긴 했는데...
안되는 이유는 2개였다.
1) 각 퀸에 대해서 퀸이 갈 수 있는 대각선, 행, 열 모두 위험지역으로 visited에 넣고 있었다. 이때 처음에 visited를 boolean으로 했다가 몇몇의 퀸에 의해서 공격지역이 겹쳐버리면 그 중 하나의 퀸을 치워도 여전히 거기는 위험지역이다. 따라서 위험지역 겹치는 카운트도 필요하다.
2) 행,열을 색칠하는 fill과 대각선 색칠 fill이 있는데 현재 퀸의 위치에 대해서 2번 색칠되고 있었다.
3) 위험지역인지 아닌지 판단하여 해당 퀸을 그 자리에 놓을려할때, check이 퀸이 가고자하는 그 후보군에 대해서만 위험지역인지 아닌지 판단해야되는데 미쳐서 해당 후보지에 퀸을 놓았을때 그 후보지에 놓은 퀸이 움직일 수 있는 공간과 위험지역이랑 하나라도 겹치는지를 보고 있었다.
애초에 2차원 배열로 푸는 문제가 아니다. 대각선에 대하여 위험지역 확인 및 색칠, 지우기 모두 일반 행,열의 로직과 비슷하다면 2차원배열로 푸는 방법도 가능하지만 나처럼 풀면 안된다.
import java.util.*;
import java.io.*;
class Solution {
static int T;
static int N;
static int ans;
static int[][] visited;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
for (int l = 0; l < T; l++) {
N=Integer.parseInt(br.readLine());
ans=0;
for(int i=0; i<N; i++){
visited = new int[N][N];
fillCol(0,i);
fillRow(0,i);
fillDiagonal(0,i);
dfs(1);
}
System.out.printf("#%d %d\n",l+1,ans);
}
}
public static void dfs(int depth){
if(depth == N){
ans++;
return;
}
for(int i=0; i<N; i++){
if(checkRow(depth,i) && checkCol(depth,i) && checkDiagonal(depth,i)){
fillCol(depth,i);
fillRow(depth,i);
fillDiagonal(depth,i);
dfs(depth+1);
eraseCol(depth,i);
eraseRow(depth,i);
eraseDiagonal(depth,i);
}
}
}
public static boolean checkRow(int a , int b){
for(int i=0; i<N; i++){
if(visited[a][i]>0){
return false;
}
}
return true;
}
public static boolean checkCol(int a, int b){
for(int i=0; i<N; i++){
if(visited[i][b]>0){
return false;
}
}
return true;
}
public static boolean checkDiagonal(int a, int b){
int d = 0;
while(d<N){
if(a-d>=0 && b-d>=0 ) {
if(visited[a-d][b-d]>0){
return false;
}
}
if(a-d>=0 && b+d<N) {
if(visited[a-d][b+d]>0){
return false;
}
}
if(a+d<N && b-d>=0) {
if(visited[a+d][b-d]>0){
return false;
}
}
if(a+d<N && b+d<N) {
if(visited[a+d][b+d]>0){
return false;
}
}
d++;
}
return true;
}
public static void fillRow(int a, int b){
for(int i=0; i<N; i++){
visited[a][i]++;
}
}
public static void fillCol(int a, int b){
for(int i=0; i<N; i++){
visited[i][b]++;
}
}
public static void fillDiagonal(int a, int b){
int d = 0;
while(d<N){
if(a-d>=0 && b-d>=0 ) visited[a-d][b-d]++;
if(a-d>=0 && b+d<N) visited[a-d][b+d]++;
if(a+d<N && b-d>=0) visited[a+d][b-d]++;
if(a+d<N && b+d<N) visited[a+d][b+d]++;
d++;
}
}
public static void eraseRow(int a, int b){
for(int i=0; i<N; i++){
visited[a][i]--;
}
}
public static void eraseCol(int a, int b){
for(int i=0; i<N; i++){
visited[i][b]--;
}
}
public static void eraseDiagonal(int a, int b){
int d = 0;
while(d<N){
if(a-d>=0 && b-d>=0 ) visited[a-d][b-d] --;
if(a-d>=0 && b+d<N) visited[a-d][b+d] --;
if(a+d<N && b-d>=0) visited[a+d][b-d] --;
if(a+d<N && b+d<N) visited[a+d][b+d] --;
d++;
}
}
}이건 처음 풀었을때 개뻘짓 코드이다.