SW Expert Academy 2806. N-Queen -난이도 D3

-링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV7GKs06AU0DFAXB&categoryId=AV7GKs06AU0DFAXB&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1 

SW Expert Academy

-문제

8*8체스보드판이 있음, 거기 위에 퀸이 8개 있음

퀸은 완전 짱쎈 투명드래곤이기 때매 같은 행, 열, 대각선위에 있는애들 모두 공격 가능함

N Queen 문제는 뭐냐면..

N*N 짜리 보드가 있고 퀸도 N개가 놓여짐

이때 서로 다른 두 퀸이 공격하지 못하게 판 위에 퀸을 놔두는 경우의 수는?

->즉 모든 퀸들이 서로 대각, 행, 열 이 동일하지 않게 놓도록 하면된다는겅?

인풋으로

테스트케이스수

N

N...

이렇게 들어옴

(헐~ 어렵당)

---

-아이디어

일단 체스판을 N*N 이차원 행렬로 만들고..

n*n for문을 돌면서 dfs로 풀어볼까?

대각선인지 확인하는법은 현재row-비교row 의 절댓값과 현재col-비교col의 절댓값이 같으면 현재 지점과 비교 지점이 대각선상에 있다는 의미이다

퀸을 놓으려고 하는 위치가 이미 놓여진 퀸들에게 공격당할 위치인지 체크하고 아니라면 그 위치에 두고 맞다면 아예 그 위치에 퀸이 놓여진 상태(노드)는 방문조차 하지 않도록한다(찾아보니 이렇게 방문할 필요 없는 노드를 안가는것이 프루닝이라고 한다.. 프루닝은 수업때 배웠는데 막상 이렇게 보니깐 새롭다 배울 당시엔 틱택토로 배웠는데.. 개념만 알고있다가 적용된것을 보니 이런게 프루닝인가.. 싶기도하고 음.. 내가 코드를 만들어 놓고도 프루닝이 프루닝인줄도 모르고 에휴)

->무튼 처음에 이렇게 하니 n=10에서 시간초과 발생했다

->처음엔 이 공격 가능 위치에 퀸이 있는지 체크하기 위해 n*n 체스판을 만들어서 그 체스판을 for문 두개로 방문해서 체크했는데 생각해보니 이렇게할 필요가 없었다 그냥 퀸이 놓여진 위치만 저장하고 row나 col이 같은지, 대각선인지 체크만 하면됨 반복문 돌 필요x

---

-처음 코드: n=10에서 시간초과

import java.util.*;
import java.io.FileInputStream;
public class Solution {
	private static int count=0;
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			int n=sc.nextInt();
			int[][] board=new int [n][n];//체스판, 퀸이 있는곳은 1 없는곳은 0
			dfs(n,0,board,0);
			System.out.println("#"+test_case+" "+count);
			count=0;
		}
	}
	public static boolean checkQueen(int row, int col, int[][]board, int n) {//추가 불가하면 false
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(j==col||(Math.abs(i-row)==Math.abs(j-col))) {
					if(board[i][j]==1) return false;
				}
			}
		}
		return true;
	}
	public static int[][] copy(int[][]board,int n){
		int[][]copiedBoard=new int[n][n];
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				copiedBoard[i][j]=board[i][j];
			}
		}
		return copiedBoard;
	}
	public static void dfs(int n,int queenNum, int[][] board,int startRow) {
		if(n==queenNum) {
			count++;
		}else {
			for(int row=startRow;row<n;row++) {
				for(int col=0;col<n;col++) {
					if(checkQueen(row, col, board, n)) {//해당 위치 추가 가능한 경우
						int [][] copiedBoard=copy(board,n);
						copiedBoard[row][col]=1;
						dfs(n,queenNum+1,copiedBoard,row+1);
					}
				}
			}
		}
	}
}

---

-두번째 코드: 이미 놓여진 퀸 확인하는법을 변경

import java.util.*;
import java.io.FileInputStream;

public class nQueen {
	static class Location{
		private int row=-1;
		private int col=-1;
		public Location(int row, int col) {
			this.row=row;
			this.col=col;
		}
		public int getRow() {
			return this.row;
		}
		public int getCol() {
			return this.col;
		}
	}
	private static int count=0;
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			int n=sc.nextInt();
			ArrayList<Location> board=new ArrayList<Location>();//이미 놓여진 퀸의 위치
			dfs(n,0,board,0);
			System.out.println("#"+test_case+" "+count);
			count=0;
		}
	}
	public static boolean checkQueen(int row, int col, ArrayList<Location> board) {//추가 불가하면 false
		for(int i=0;i<board.size();i++) {
			int queenRow=board.get(i).getRow();
			int queenCol=board.get(i).getCol();
			if(queenRow==row||queenCol==col||Math.abs(queenRow-row)==Math.abs(queenCol-col)) {
				return false;
			}
		}
		return true;
	}
	public static ArrayList<Location> listCopy(ArrayList<Location> original){
		ArrayList<Location> copiedBoard=new ArrayList<Location>();
		for(int i=0;i<original.size();i++) {
			Location loc=original.get(i);
			copiedBoard.add(new Location(loc.getRow(),loc.getCol()));
		}
		return copiedBoard;
	}
	public static void dfs(int n,int queenNum, ArrayList<Location> board,int startRow) {
		if(n==queenNum) {
			count++;
		}else {
			for(int row=startRow;row<n;row++) {
				for(int col=0;col<n;col++) {
					if(checkQueen(row, col, board)) {//해당 위치 추가 가능한 경우
						ArrayList copiedBoard=listCopy(board);
						copiedBoard.add(new Location(row,col));
						dfs(n,queenNum+1,copiedBoard,row+1);
					}
				}
			}
		}
	}
}

---

통과는 했는데 다른사람들 코드에비해 용량도 많이쓰고  시간도 너무 많이 걸려서 다른 코드를 비교해보기로함

https://hees-dev.tistory.com/52 <- 이사람 코드를 좀 봤는데

이미 놓아진 퀸을 어떻게 보관할지 그부분이 문제였다

이미 놓아진 퀸을 저장할때 n개의 숫자를 저장하는 배열을 만들고.. 0 인덱스에서는 row=0 인거고 0인덱스에 저장한 값이 col이 되는 방식으로 하면.. 위에서처럼 퀸을 저장하는 리스트를 복사할 필요가 없어짐(복사하는 이유는 ㅠㅠ 리스트 전달할때 리스트의 주소를 보내서 원본이 가기때매 퀸 배치하는걸 찾다가 끝까지 다 본 다음에 찾기 실패했을때 보드를 리셋해야되는데 언제 리셋할지 .. 모르겠어서.. ㅋㅋ 근데 생각해보니깐 어떤 위치에 퀸 놔둔 담에 dfs갔다오고 그담에 놔둔 퀸 다시 빼면 되지 않나?)->헐 이거됨 아 나 완전 바본듯 원래 dfs에서 스택에 왔던 길 저장해두잖음 정답 찾기 실패했을때 되돌아갈라고... board가 스택 역할을 하는거임.. 

package al;
import java.util.*;
import java.io.FileInputStream;

public class nQueen {
	static class Location{
		private int row=-1;
		private int col=-1;
		public Location(int row, int col) {
			this.row=row;
			this.col=col;
		}
	}
	private static int count=0;
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			int n=sc.nextInt();
			ArrayList<Location> board=new ArrayList<Location>();//이미 놓여진 퀸의 위치
			dfs(n,0,board,0);
			System.out.println("#"+test_case+" "+count);
			count=0;
		}
	}
	public static boolean checkQueen(int row, int col, ArrayList<Location> board) {//추가 불가하면 false
		for(int i=0;i<board.size();i++) {
			int queenRow=board.get(i).row;
			int queenCol=board.get(i).col;
			if(queenRow==row||queenCol==col||Math.abs(queenRow-row)==Math.abs(queenCol-col)) {
				return false;
			}
		}
		return true;
	}
	public static void dfs(int n,int queenNum, ArrayList<Location> board,int startRow) {
		if(n==queenNum) {
			count++;
		}else {
			for(int row=startRow;row<n;row++) {
				for(int col=0;col<n;col++) {
					if(checkQueen(row, col, board)) {//해당 위치 추가 가능한 경우
						board.add(new Location(row,col));
						dfs(n,queenNum+1,board,row+1);
						board.remove(board.size()-1);
					}
				}
			}
		}
	}
}

 

위가 복사부분 없앤거고 밑에가 복사 있는거

여전히 별로

---

-세번째 코드: 남의 코드 참고하자...

위에서 말한 https://hees-dev.tistory.com/52 이사람 코드에서 퀸을 저장하는 방식을 참고해서 다시 해보겠다

이 방식을 사용하면 Location class를 따로 만들 필요 없다 (근데 생각해보니깐.. 클래스 안만들고 걍 두칸짜리 배열쓰면되자늠.. ㅋㅋㅋ 하..짱나네) 이거지금 해보겠음

package al;
import java.util.*;
import java.io.FileInputStream;

public class nQueen {
	private static int count=0;
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			int n=sc.nextInt();
			ArrayList<int[]> board=new ArrayList<int[]>();//이미 놓여진 퀸의 위치
			dfs(n,0,board,0);
			System.out.println("#"+test_case+" "+count);
			count=0;
		}
	}
	public static boolean checkQueen(int row, int col, ArrayList<int[]> board) {//추가 불가하면 false
		for(int i=0;i<board.size();i++) {
			int queenRow=board.get(i)[0];
			int queenCol=board.get(i)[1];
			if(queenRow==row||queenCol==col||Math.abs(queenRow-row)==Math.abs(queenCol-col)) {
				return false;
			}
		}
		return true;
	}
	public static void dfs(int n,int queenNum, ArrayList<int[]> board,int startRow) {
		if(n==queenNum) {
			count++;
		}else {
			for(int row=startRow;row<n;row++) {
				for(int col=0;col<n;col++) {
					if(checkQueen(row, col, board)) {//해당 위치 추가 가능한 경우
						board.add(new int[] {row,col});
						dfs(n,queenNum+1,board,row+1);
						board.remove(board.size()-1);
					}
				}
			}
		}
	}
}

 

맨 위에가 클래스 없애고 걍 배열로한건데 역시나 ..별로

---

-이번엔 진짜 저사람 코드 참고해봄^^! 

package al;
import java.util.*;
import java.io.FileInputStream;

public class nQueen {
	private static int count=0;
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			int n=sc.nextInt();
			int [] board=new int[n];//이미 놓여진 퀸의 위치
			for(int i=0;i<n;i++) 
				board[i]=-1;
			dfs(n,board,0,0);
			System.out.println("#"+test_case+" "+count);
			count=0;
		}
	}
	public static boolean checkQueen(int row, int col, int[] board) {//추가 불가하면 false
		for(int i=0;i<row;i++) {
			if(col==board[i]||Math.abs(i-row)==Math.abs(board[i]-col))
				return false;
		}
		return true;
	}
	public static void dfs(int n, int[] board,int startRow, int queenNum) {
		if(n==queenNum) {
			count++;
		}else {
			for(int row=startRow;row<n;row++) {
				for(int col=0;col<n;col++) {
					if(checkQueen(row, col, board)) {//해당 위치 추가 가능한 경우
						board[row]=col;
						dfs(n,board,row+1,queenNum+1);
					}
				}
			}
		}
	}
}

맨 위에 211ms가 퀸 저장법 바꾼거 

-비교

마지막 코드랑(배낀거 아니 참고한거) 네번째코드는 반복문의 수가 차이 없는데 왜 이렇게 시간이 다른가(211vs1111)

궁금해서 찾아봄

https://yeon-kr.tistory.com/152

(Java)ArrayList vs LinkedList 시간 복잡도

https://jayyhkwon.github.io/java/2019/10/31/Java-ArrayList-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84/

ArrayList 시간복잡도 · jayyhkwon의 개발공부로그

https://waristo.tistory.com/8

[시간복잡도, 공간복잡도] ArrayList vs LinkedList

이 블로그들을 봤는데..

 ArrayList에서 get은 시간복잡도가 O(1)으로 (인덱스를 알고있기 때문에 랜덤엑세스) 얘 때문은 아니고

 add도 인덱스로 특정 위치에서 값 추가는 O(n)이지만.. 맨끝에 넣는건 O(1)로 얘 때문도 아니고

문제는 remove였음 remove를 하려면 O(n)의 시간이 걸린다..

왜냐면 지우고 나서 남아있어야 하는 부분을 복붙하는데 O(n-1)=O(n) 이 걸리는듯? 아마..

---

-교훈

뭔가 숫자 하나와 어떤 값의 쌍을 저장할일이 있으면 int 배열을 쓰자

배열 길이를 미리 알수있다면.. 웬만하면 고정길이 배열을 쓰자.. 

dfs를 쓸때.. 스택.. 제발.. 스택 만들때 스택을 배열로 할거면 top을 저장해서 top까지만 있다 이런식으로 해야.. (위 코드에서 는 row가 top의 역할을 함)

아니근데 애시당초 자바에 스택을 제공하잖음?.. 하..... 자고일어나서해봄이건

 

 

푸는것 자체는 2시간 걸렸는데... 다듬느라 4시간 걸렸넹 벌써 새벽 4시다.. 오늘도 일찍 자기 실패다

항상일찍 자려고.. 하는데 코딩 이런거에 집중하다보면 시간이 금방 가있다.. 좋은건지 나쁜건지..

코테라는거슨.. 재밌긴한데.. 이걸 제한시간안에 풀라고하니깐.. 자닌해.. 

근데 하다보니깐.. 생각난건데 이거 멀티버스같지않음? 형제 노드가 지금 상태의 멀티버스인 상황인거고 자식노드는 시간이 흐른 뒤 인거임 ㅋㅋ 그니깐 dfs bfs는 멀티버스다? ㅋㅋ .. 에휴.. 빨리 자야겠다