자료구조 과제로 나온 nqueen problem 풀이를 하다가 죽을 뻔 했다.
재귀를 짜는 것도 어려웠는데 나 같은 경우에는 queen을 놓아도 되는지. 그러니까 양옆 대각선으로 퀸이 자리 하고 있는지를 검사하는 함수를 짜는게 제일 어려웠다.
동아리 오빠들이 direction으로 짜서 어떻게 하라고 하는데, 나는 아직 그런 방법이 익숙하지가 않아서
나만의 방법으로 처음 했었다.
좌표계에서 좌표를 찍듯이 해서 약간 y=f(x) 함수 짜듯이 해서 메소드를 만들었었는데,
그렇게 하니까 오류가 떠서 아예 새로운 방법으로 갈아엎었다.
그래서 선배들이 알려준 direction을 사용한 방식을 썼는데 나는 아직도 무슨 소리인지 잘 모르겠다.
하지만 그래도 이렇게 체스보드 클래스를 짜보기도 하고, 이런 어려운 문제들도 풀다보니까 실력이 많이 향상 된 것 같다.
다음은 nqueensolver 파일 내용이고,
public final class NQueenSolver implements INQueenSolver {
@Override
public Chessboard solve(Chessboard chessboard) {
int size=chessboard.size();
for (int i=0; i<size; i++) {
for (int j=0; j<size; j++) {
if (chessboard.getCell(i, j)==Chessboard.CellState.QUEEN)
{
chessboard.setCell(i,j,Chessboard.CellState.EMPTY);
boolean currAvail=avail(chessboard, i, j, size);
if (!currAvail) {
return new Chessboard(size);
}
chessboard.setCell(i,j,Chessboard.CellState.QUEEN);
}
}
}
Chessboard result=nqueen(chessboard, 0);
if (result==null) {
return new Chessboard(size);
} else {
return result;
}
}
public Chessboard nqueen(Chessboard chessboard, int row) {
int size = chessboard.size();
if (row == size) {
return chessboard;
} else {
for (int col = 0; col < size; col++) {
if (chessboard.getCell(row, col) == Chessboard.CellState.QUEEN) {
return nqueen(chessboard, row + 1);
} else {
boolean currAvail = avail(chessboard, row, col, size);
if (currAvail) {
chessboard.setCell(row, col, Chessboard.CellState.QUEEN);
Chessboard newrow = nqueen(chessboard, row + 1);
if (newrow != null) {
return newrow;
} else {
chessboard.setCell(row, col, Chessboard.CellState.EMPTY);
}
}
}
}
}
return null;
}
public boolean avail(Chessboard chessboard, int i, int j, int size) {
int row = i;
int col = j;
Chessboard board = chessboard;
int[] rowDir = {-1, 1, 0, 0, -1, 1, 1, -1};
int[] colDir = {0, 0, 1, -1, 1, 1, -1, -1};
Chessboard.CellState curCell = board.getCell(row, col);
if (curCell != Chessboard.CellState.QUEEN) {
for (int d = 0; d < 8; d++) {
int curRow = row + rowDir[d];
int curCol = col + colDir[d];
while (0 <= curRow && curRow < size && 0 <= curCol && curCol < size) {
if (board.getCell(curRow, curCol) == Chessboard.CellState.QUEEN) {
return false;
}
int nextRow = curRow + rowDir[d];
int nextCol = curCol + colDir[d];
curRow = nextRow;
curCol = nextCol;
}
}
}
return true;
}
}
이거는 체스보드 클래스다.
public final class Chessboard implements Cloneable {
public static enum CellState {
EMPTY,
QUEEN
};
private int size;
private CellState[] board;
public Chessboard(int size) {
this.size = size;
board = new CellState[size * size];
for (int i = 0; i < board.length; ++i)
{
board[i] = CellState.EMPTY;
}
}
private int cellToIdx(int i, int j) {
return i * size + j;
}
public CellState getCell(int i, int j)
throws IndexOutOfBoundsException {
if (i < 0 || j < 0 || i >= size || j >= size)
throw new IndexOutOfBoundsException(
String.format("(%d, %d)", i, j)
);
return board[cellToIdx(i, j)];
}
public void setCell(int i, int j, CellState state)
throws IndexOutOfBoundsException {
if (i < 0 || j < 0 || i >= size || j >= size)
throw new IndexOutOfBoundsException(
String.format("(%d, %d)", i, j)
);
board[cellToIdx(i, j)] = state;
}
public int size() {
return size;
}
public Chessboard clone() {
try {
Chessboard o = (Chessboard)super.clone();
o.board = this.board.clone();
return o;
}
catch (CloneNotSupportedException ex) {
return null;
}
}
}어려워 죽는 줄 알았는데 그래도 한 네시간? 만에 해냈다.
근데 중간에 한 시간 정도 vscode에서 디버깅이 안돼서 계속 헤맸다..ㅠㅠㅠ
검색해봐도 어떻게 하라는 건지 잘 모르겠어서 이제부터 그냥 터미널에 javac `~~.java
이런식으로 직접 컴파일하고 java ~~~ 이렇게 직접 실행하는 방법을 쓰기로 했다.
원래 이렇게 터미널에 어떻게 하는 건지 잘 몰랐는데
동아리 선배가 ls, cd, 등등 터미널 언어? cli? 맞나 암튼 그런거랑 컴파일 어떻게 하는지 이런 것도 다 알려줘서
이제부터는 그냥 디버깅 툴?을 안쓰고 직접 타이핑해서 하려고 한다!
처음에 대충 틀을 완성해냈을 때, 자잘한 문법오류들을 고치니까 돌아는 가는데 테스트 케이스에서 오류가 몇개 났었다.
테스트 케이스에서 오류가 나는 경우를 생각해보니까
완전 처음부터 불가능한 경우가 들어오는 것을 고려하지 않고 코드를 짰어서
코드 앞부분에, 처음부터 불가능할 때는 재귀를 돌리지 않는 다는 내용의 코드를 추가했다.
댓글