SW Expert Academy 2806 N-QUEEN

N-QUEEN링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB

SW Expert Academy

오늘은 백준 홈페이지가 터져서 SW Expert에 있는 N-QUEEN을 풀어봤어요.

백트래킹을 공부해봤다면 흔히 아는 그 N-QUEEN맞습니다.

문제난이도가 D-3라서 가볍게 D-3하나먹고 깔끔하게 시작하려고 했는데 두시간이나 걸렸네요 ㄷㄷ(심지어 시간도 공간도 많이 잡아 먹어버렸다능....ㅠㅠ)

 

문제에 대하여 깔짝 설명 하자면 NXN크기의 맵에 N개의 QUEEN(체스말)을 놓는데 어느것 하나 죽지않게 놓을 수 있는가짓수를 찾는거였어요.

 

따라서 브루트 포스에 가지치기를 해야 했는데 일단 저는 Arraylist에 좌표값을 넣어준 int[]배열을 넣어서  관리를 했습니다.

 

몇가지 아이디어로

1. list에 좌표를 넣어줄때 이미들어가있는 좌표들과 비교했을때 새로운 좌표의 X또는 Y가 중복이 되면 안됩니다. (중복이 된다면 QUEEN은 가로 세로 대각선으로 이동이 가능하기때문에 잡아 먹힐꺼에요)

 

2. 저는 재귀함수를 사용했는데 list의 size가 N이되면 각각의 좌표에 대하여 대각선의 방향을 체크해줍니다(1번은 가로 세로에 대하여 비교를 한것이기 때문에 대각선은 따로 비교해줬어요)

 

3.좌표들은 y에 대하여 오름차순으로 list에 들어가 있기 때문에 사실 윗쪽 대각선은 비교할 필요가 없습니다(만약 이동경로에 있다면 이전 좌표에서 걸리겠죠ㅋ)

다음과 같은 N이 4인 맵에 list에 1->2->3->4 순서 대로 들어가 있다고 가정한다면

1을 대각선,가로,세로 로 비교해보았을때 보라색 영역 처럼 되기때문에 3번은 굳이 윗쪽대각선을 비교하지 않아도 1번 좌표에서 이미 걸리므로 굳이 비교해볼 필요없이 아랫쪽 대각선만 생각하시면 됩니다

 

그럼 코드를 볼까용?

사실 문제에대한 코드는 무척 쉽습니다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.StringTokenizer;

public class NQueen {

	static List<int[]> positionStorage = new ArrayList();// 각각의 좌표를 넣어줄 리스트
	static int N = 0;
	static int answer = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int TC = Integer.parseInt(st.nextToken());

		for (int t = 1; t <= TC; t++) {
			positionStorage.clear();
			N = Integer.parseInt(br.readLine());
			answer = 0;
			CountCases(0, 1);
			System.out.println("#" + t + " " + answer);
		}
	}

	private static void CountCases(int count, int paramY) {
		if (count == N) {
			// 대각선의 방향을 체크해주는 로직
			if (checkDiagnal()) {
				answer++;
			}
			return;
		}
		int y = paramY;

		for (int x = 1; x <= N; x++) {
			boolean checkX = false;
			for (Iterator<int[]> iter = positionStorage.iterator(); iter.hasNext();) {
				if (x == iter.next()[1]) {
					checkX = true;
					break;
				}
			}
			if (checkX) {
				continue;
			}
			positionStorage.add(new int[] { y, x });
			CountCases(count + 1, y + 1);
			positionStorage.remove(positionStorage.size() - 1);
		}
	}

	private static boolean checkDiagnal() {
		for(int i=0; i<N; i++) {
			int[] position = positionStorage.get(i);
			for(int j=i+1; j<N; j++) {
				int[]temp = positionStorage.get(j);
				if (Math.abs(position[0] - temp[0]) == Math.abs(position[1] - temp[1])) {
					return false;
				}
			}
		}
		return true;
	}

}

 다만 다른사람들과 시간과 메모리를 비교해봤을때 월등히 안좋은 코드더라구요;;;

혹시 코드상에서 최적화 가능하신분은 댓글남겨주시면 감사하겠습니다 ㅎㅎ!!