🕦 풀이시간 : 1시간 30분
😥 실패 및 원인
마지막까지 고민했을 때까지도 확실하게 파악하지 못한 것이 반복을 어떻게 진행할 것인지가 막막했다.
처음에 시작을 하면은 가로로도, 세로로도 쭉 나올 수 있고 그 나온 다음에 그림이 어떻게 될 지 확실한 기준을 못 잡았다. 계속 그림을 그리면서 이해해보려했는데 생각보다 잘 안되었다..
❌ 2차원 배열에 저장해야해...
거의 틀에 박힌 생각이었던 게 2차원 배열에서 내가 선택한 부분에 대해서는 1로 전부 표시를 해두어야겠다는 고정된 사고에서 벗어나지 못한 게 좀 큰 것 같다..저런 식으로 꼭 지나간 자리들을 전부 표시하지 않더라도 좋은 방법이 있었다.
❌ 과정을 거칠때마다 기록해야해..
한 공간을 차지할 때마다 배열에 1을 기록해야한다면 그것은 그것대로 시간이 엄청 많이 걸릴 뿐만 아니라 처리하기에도 복잡했다. 가로랑 세로까지는 어떻게든 할 수 있었지만 문제는 대각선이었다. 대각선의 경우 고심하다가 생각한 게 정한 지점에서 왼쪽 끝에 붙었을 때(y = 0)이 되는 두 지점을 찾도록 (-1,-1), (-1,+1)을 while로 돌려서 벽에 붙고 쭉 대각선으로 이동하면서 1을 기록하려고 했다.
시도하다가 다시 하려고 다 지워버려서 해당 코드는 없지만..
이 방법은 아니겠다 싶었던 게 이 기록을 했다면 다시 이것을 0으로 바꾸어두어야 할텐데 그 부분에서 "아..이렇게까지는 할 문제가 아닐 것 같다" 싶어서 돌아서게되었다.
private static void DFS(int x, int y, int depth) {
if(depth == N) {
cnt++;
return;
}
//가능한 지 탐색
for(int i = 0; i < N; i++){
if(board[i][depth] == 0){
//TODO : 관련 모두 1
DFS(0,0,depth+1);
//TODO : 했던 1을 0으로
}
}
//가능한 지 탐색
for(int i = 0; i < N; i++){
board[depth][]
}
}import java.io.*;
import java.util.*;
import static java.lang.System.exit;
/*
* 퀸이 서로 공격할 수 없게 놓는 문제!
* DFS(0,0) => if(둘 곳이 없) return if(완성)
* 체스판에 가로,세로,대각을 1로 변경
*
* */
public class Main {
static int cnt = 0;
static int N;
static int[][] board;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
board = new int[N][N];
DFS(0,0,0);
System.out.print(cnt);
}
private static void DFS(int x, int y, int depth) {
if(depth == N) {
cnt++;
return;
}
//가능한 지 탐색
for(int i = 0; i < N; i++){
if(board[i][depth] == 0){
//TODO : 관련 모두 1
DFS(0,0,depth+1);
//TODO : 했던 1을 0으로
}
}
//가능한 지 탐색
for(int i = 0; i < N; i++){
board[depth][]
}
}
}
💡 해결을 위한 과정
📌 2차원 배열 저장을 포기 & 저장 방법
2차원 배열로 저장하고 한 번 퀸을 둔 위치에는 반드시 1로 표시를 해야지 다른 퀸이 놓을 자리를 쉽게 찾을 수 있을거라 생각했다.
하지만 그 과정 자체가 너무나 번거롭고 비효율적으로 되어갔기에 2차원 배열을 포기했다.
그 후 1차원 배열로 표기를 했다.
이런 상태라면 board = {2,0,3,1}이 담기는 것이다.
즉 인덱스 자체가 어떤 열인지를 말해주고 있는 것이다.
이해하는데 조금 시간이 걸렸는데
- board[0] = 2
- board[1] = 0
- board[2] = 3
- board[3] = 1
이러면 좀 쉽게 이해가 된다.
2번째 행에서 0번째 열이 (사실상board[2][0])에 퀸을 놓았다는 의미이다!
📌 현재 놓을 수 있는 위치인지 확인!
위에서 언급했 듯이 1차원 배열로 두었기 때문에 현재 위치를 확인하는데 있어 행 확인은 매우 쉽다!
행이 겹치는가?
반복문 N번 수행하는데 있어서
if(board[i] == board[curDepth])
break;열이 겹치는가?
열을 기준으로 계속 만들어왔기 때문에 열은 애초에 겹칠 수가 없다!!
이런 부분이 1차원 배열에서 큰 이점인 것 같다!
대각선 확인
이건 사실 코드를 바로 보고도 딱 이해가 안됬다.
뭐랄까 느낌은 오는데 머리속으로 완벽 이해는 아닌!
이 부분에서 다시 한 번 풀어봐야겠다고 생각하게 되었다!
//대각선에 해당하는 위치인지?
else if (Math.abs(col - i) == Math.abs(board[col] - board[i])) {
return false;
}👍 대각 이해하기
4X4에서 3번째열에 두자고 해보자!
첫번째 행은 안된다!(가로행)
두번째 행 안된다!(대각)
일단 지금 경우는 행에서 겹치지 않는다! 그럼 대각 검증 코드로 내려오게 될텐데
현재 검증이 필요한 위치에서 반복문 i를 이용해서 검증을 시작한다!
- 첫 번째 열 board[0][2]
col = 2
i = 0
board[col] = 1
board[i] = 2
(2 - 0) == (0 - 2) -> 성립 안하니까 넘어간다
- 두 번째 열 board[0][1]
col = 2
i = 1
board[col] = 1
board[i] = 0
(2 - 1) == (1 - 0) -> 일치하는 것은 대각에 위치한다는 것! false를 리턴하자!
현재 위치에서 떨어진 위치(인덱스 위치)만큼 실제 저장된 배열에서도 같은 거리에 있다면 안된다는 의미이다!
성공 코드
import java.io.*;
import java.util.*;
import static java.lang.System.exit;
/*
* 서로 공격할 수 없는 N퀸
* 2차원 배열로 진행하지 않고 1차원 배열 형태로 진행한다!
*
* 반복
* 1.종료조건인지 파악한다(depth)
* 2.현재 열에서 봤을 때 놓을 수 있는 지!
* 2.이 전 대각선에 비해서 놓을 수 있는 지?
*
* */
public class Main {
static int cnt = 0;
static int N;
static int[]board;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
board = new int[N];
DFS(0);
System.out.print(cnt);
}
private static void DFS(int depth) {
if(depth == N) {
cnt++;
return;
}
//가능한 지 탐색
for(int i = 0; i < N; i++){
board[depth] = i;
//이 전 것들을 모두 고려해서 놓을 수 있는 위치를 찾자!
if(isPossible(depth)){
DFS(depth+1);
}
}
}
private static boolean isPossible(int col) {
//지금까지 둔 N퀸의 위치를 생각해서 놓을 수 있는 위치를 찾자!
for(int i = 0 ; i < col; i++){
//가로 세로가 가능한 위치인지?
if(board[i] == board[col]){
return false;
}
//대각선에 해당하는 위치인지?
else if (Math.abs(col - i) == Math.abs(board[col] - board[i])) {
return false;
}
}
return true;
}
}
