BOJ#9663 N-Queen

BOJ#9663 N-Queen

* 문제

https://www.acmicpc.net/problem/9663

* 풀이

유명하면서도 어려운 문제입니다.

Queen을 1개~N개까지 배치하면서, 잘못 배치한 경우 되돌아가서 다른 시도를 해봐야 합니다. 

따라서 backTracking을 이용합니다.

주의할 점

0. Queen

Queen은 상하좌우, 대각선 모두 이동할 수 있습니다.

1. 꼭 행렬로 map을 만들 필요가 없습니다.

보통 map 행렬을 만든 후 -1, 0, 1등의 숫자를 이용해

배치할 수 있는 곳과 아닌 곳을 표시하고, 이 정보를 기반으로 다음 행동을 결정하는데

이 경우 불필요한 리소스와 시간이 소요됩니다.

2. Queen은 N개 이므로 행(row) 1개당 Queen 1개가 배치됩니다.

 = 각 행마다 Queen이 배치될 Column 결정하는 문제

따라서 int[] column = new int[N] 을 만들어줍니다.

column[0] = 0행에서 0번째 queen이 위치한 column

column[1] = 1행에서 1번째 queen이 위치한 column

column[2] = 2행에서 2번째 queen이 위치한 column

...

column[N-1] = N-1행에서 N-1번째 queen이 위치한 column

3. Queen을 (targetRow, targetCol)에 배치할 때, 해당 위치가 안전한지 판단해야 합니다.

특히 대각선의 경우 어떻게 간단히 판별할지 고민이 필요합니다.

1) 열 검사

이전에 위치한 Queen들과 같은 열에 위치하면 안됩니다.

for ( row = 0 ; row < targetRow ; row++) {

column[row] == targetCol ?

}

2) 대각선 검사

이전에 위치한 Queen들과 대각선에 위치하면 안됩니다.

for ( row = 0 ; row < targetRow ; row++) {

targetRow - row == Math.abs(targetCol - column[row] ?

}

3) 행 검사

행 검사는 할 필요가 없습니다. 위에서 말했듯이 행마다 Queen이 1개씩 위치하기 때문입니다.

Solution#1 (시간 초과)

- ArrayList에 int가 아닌 Integer 객체를 생성해서 넣어줘야 합니다. 그래야 ArrayList에서 원하는 Object를 삭제할 수 있습니다.

- (Line 44) row++가 아니라 row+1을 해줘야 합니다. row++을 하면 다음 Iteration에서 row값이 변경된채로 진행됩니다.

- (Line 45) 다음 Iteration을 위해 변경사항을 원복해줍니다.

public class Main_TLE { public static void main(String[] args) throws IOException { int N; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); ChessBoard chessboard = new ChessBoard(N); chessboard.findSolution(); System.out.println(chessboard.getNumOfSoltion()); } } class ChessBoard { private Solution solution; private int size; private int numOfSolution; public ChessBoard(int n) { this.solution = new Solution(); this.size = n; this.numOfSolution = 0; } private void backTracking(int row) { if (row >= size) { numOfSolution++; return; } for (int col = 0; col < size; col++) { if (row == 0 || solution.isSafePlace(row, col)) { Queen queen = new Queen(row, col); solution.addQueen(queen); backTracking(row + 1); solution.removeQueen(queen); } } } public void findSolution() { backTracking(0); } public int getNumOfSoltion() { return numOfSolution; } } class Solution { // private ArrayList<Integer> row = new ArrayList<Integer>(); private ArrayList<Integer> col = new ArrayList<Integer>(); private ArrayList<Integer> diagLeft = new ArrayList<Integer>(); private ArrayList<Integer> diagRight = new ArrayList<Integer>(); public Solution() { } public boolean isSafePlace(int x, int y) { /* if (row.contains(x)) { return false; } */ if (col.contains(y)) { return false; } if (diagLeft.contains(x - y)) { return false; } if (diagRight.contains(x + y)) { return false; } return true; } public void addQueen(Queen queen) { //row.add(new Integer(queen.getX())); col.add(new Integer(queen.getY())); diagLeft.add(new Integer(queen.getX() - queen.getY())); diagRight.add(new Integer(queen.getX() + queen.getY())); } public void removeQueen(Queen queen) { //row.remove(new Integer(queen.getX())); col.remove(new Integer(queen.getY())); diagLeft.remove(new Integer(queen.getX() - queen.getY())); diagRight.remove(new Integer(queen.getX() + queen.getY())); } } class Queen { private int x, y; public Queen(int x, int y) { this.setX(x); this.setY(y); } public int getX() { return x; } public void setX(int x) { this.x = x; } public int getY() { return y; } public void setY(int y) { this.y = y; } }

Solution#2 (메모리 : 17440 KB , 시간 : 6540 MS)

- 시간 초과 때문에 ArrayList를 버리고 간단하게 isSafePlace()함수를 구현했습니다.

- (Line 57) loop 반복 조건에서 row < N이 아니라 row < targetRow를 해주면 불필요한 loop를 피할 수 있습니다.

public class Main { public static void main(String[] args) throws IOException { int N; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); NQueen queen = new NQueen(N); queen.findSolution(); System.out.println(queen.getNumOfSolution()); } } class NQueen { private int[] column; private int size; private int numOfSolution; public NQueen(int N) { this.size = N; this.column = new int[N]; this.numOfSolution = 0; clearColumn(); } private void backTracking(int row) { if (row >= size) { numOfSolution++; return; } for (int col = 0; col < size; col++) { if (isSafePlace(row, col)) { column[row] = col; backTracking(row + 1); column[row] = -1; } } } private boolean isSafePlace(int targetRow, int targetCol) { if (targetRow < 1) { return true; } for (int row = 0; row < targetRow; row++) { if (column[row] == targetCol || targetRow - row == Math.abs(targetCol - column[row])) { return false; } } return true; } public void findSolution() { backTracking(0); } private void clearColumn() { for (int i = 0; i < size; i++) { column[i] = -1; } } public int getNumOfSolution() { return numOfSolution; } }

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%239663_NQueen