SWEA[2806] - N-Queen[D3]

링크

SWEA[2806]

문제설명

• 백트래킹

문제풀이

• 백트래킹, 수직, 좌상, 우상 체크

문제코드(2차원배열)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Solution2806 {
    public static int[][] map;
    public static int[] hor;
    public static int Ans;
    public static int N;
    public static boolean is_possible(int r, int c) {
        int nr;
        int nc;
//        수직
        for (int i = 1; i <= r; i++) {
            nr = r-i;
            nc = c;
//            경계 안이고, 놓을 수 없을 때
            if(nr>=0 && nr<N && nc>=0 && nc<N) {
                if(map[nr][nc]!=0) {
                    return false;
                }
            }
        }

//        좌상 대각선
        for (int i = 1; i <= r; i++) {
            nr = r-i;
            nc = c-i;
//            경계 안이고, 놓을 수 없을 때
            if(nr>=0 && nr<N && nc>=0 && nc<N) {
                if(map[nr][nc]!=0) {
                    return false;
                }
            }
        }
//        우상 대각선
        for (int i = 1; i <= r; i++) {
            nr = r-i;
            nc = c+i;
//            경계 안이고, 놓을 수 있을 때
            if(nr>=0 && nr<N && nc>=0 && nc<N) {
                if(map[nr][nc]!=0) {
                    return false;
                }
            }
        }
        return true;
    }
    public static void NQ(int r) {
        if(r==N) {
            Ans++;
            return;
        }
        for (int i = 0; i < N; i++) {
//            놓을 수 있는 자리면
            if(is_possible(r,i)) {
                map[r][i]=1;
                NQ(r+1);
                map[r][i]=0;
            }
        }
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/swea/2806.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T=Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            N = Integer.parseInt(br.readLine());
            map = new int[N][N];
            hor = new int[N];
            NQ(0);
            System.out.println("#"+test_case+" "+Ans);
            /*
             * 초기화
             */
            Ans=0;
        }//end test_case
    }//end main
}//end class

문제코드(1차원배열)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Solution2806_sol {
    public static int[] row;    // 몇 번째 row에서 선택했는지 저장
    public static int Ans;
    public static int N;
    public static boolean is_possible(int r,int c) {
        for (int i = 0; i < r; i++) {
//            놓을 수 없을 때
            if(    c==row[i] ||    //수직
                Math.abs(c-row[i])==(r-i)    //대각선
                ) {
                return false;
            }
        }
        return true;
    }
    public static void NQ(int r) {
        if(r==N) {
            Ans++;
            return;
        }
        for (int i = 0; i < N; i++) {
//            놓을 수 있는 자리면
            if(is_possible(r,i)) {
                row[r]=i;
                NQ(r+1);
                row[r]=-1;    //굳이 안해도 됨 어차피 덮어쓸꺼니까
            }
        }
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/swea/2806.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T=Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            N = Integer.parseInt(br.readLine());
            row = new int[N];
            for (int i = 0; i < N; i++) {
                row[i]=-1;
            }
            NQ(0);
            System.out.println("#"+test_case+" "+Ans);
            /*
             * 초기화
             */
            Ans=0;
        }//end test_case
    }//end main
}//end class

아쉬운점

• 체크할 때 인덱스 끝까지 안갔음
• 2차원말고 1차원으로 푸는 풀이 있는데 모르겠음

잘한점

• 하긴 함

다른 풀이

• 1차원 배열에 몇번 열에 퀸을 놓는지에 대한 정보를 저장하면 풀 수 있음.