[백준] 9663.N-Queen / BackTracking

@BackTracking / 1h

나이트랑 헷갈려서 바보짓 하고.. 이후에 이전 코드 보고 다시 풀었음 ㅜㅜ

 

문제 링크

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

9663번: N-Queen

 

 

참고 자료

퀸의 공격 범위 : 수직, 수평선 및 대각선 4방향

즉, 아래에서 검은색으로 표시된 칸에는 다른 퀸을 놓을 수 없다.

출처 : http://blog.daum.net/tomayoon/7089880

 

 

구현 포인트

처음에 visit 표시를 어떻게 하지 고민이 많았다

만약 단순히 backTracking으로 true/false를 하면, 지금 단계가 아니라 이전 단계에서 표시한 visit까지 지워질 것이기 때문에

 

이를 해결하려면 visit배열을 int형으로 선언하면 된다!

visit을 표시할 때는 +1, 지울 때는 -1을 해주면

지금 단계가 지워지더라도 만약 양수라면 이전 단계의 말 때문에 놓을 수 없는 칸이 되기 때문이다.

(visit이 음수가 될 수는 없다. 표시한 곳만 지우기 때문에)

 

그리고 이렇게 하면 표시할 때, 지울 때를 각각 분리해줄 필요 없이 + val 이런식으로 표시하면

매개변수에 따라서 알아서 +1이 되거나 -1이 돼서 코드가 훨씬 간단해진다!

 

 

 

예전 코드

import java.util.Scanner;

public class Main {

	static int size, count = 0;
	static int[][] map;
	static boolean[][] visit;

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		size = s.nextInt();

		map = new int[size][size];
		visit = new boolean[size][size];

		//첫 열에서 시작, 시작부분만 depth를 0으로 고정
		for (int i = 0; i < size; i++) {
			check(i, 0, true, 1);
			backTracking(1);
			check(i, 0, false, 1);
		}
		System.out.println(count);
	}

	//다음 열로 전진하는 코드
	private static void backTracking(int depth) {
		//print();
		//열의 끝까지 depth가 갔으면 count 해준 뒤 종료
		if (depth == size) {
			count++;
			return;
		}

		for (int i = 0; i < size; i++) {
			if (map[i][depth] == 0) {
				check(i, depth, true, depth + 1);
				backTracking(depth + 1);
				check(i, depth, false, depth + 1);
				//print();
			}
		}
	}
	
	//들어갈 수 없는 자리에 표시해주는 코드
	private static void check(int x, int y, boolean flag, int depth) {
		// 가로줄 체크
		for (int i = y; i < size; i++) {
			//전진하는 거면 표시하고
			if (flag) {
				if (map[x][i] == 0) {
					map[x][i] = depth;
				}
			//돌아오는 거면 지워라(0으로)
			} else {
				if (map[x][i] == depth) {
					map[x][i] = 0;
				}
			}
		}
		// 대각선 위쪽 체크
		for (int i = 1; x - i >= 0 && y + i < size; i++) {
			if (flag) {
				if (map[x - i][y + i] == 0) {
					map[x - i][y + i] = depth;
				}
			} else {
				if (map[x - i][y + i] == depth) {
					map[x - i][y + i] = 0;
				}
			}
		}
		//대각선 아래쪽 체크
		for (int i = 1; x + i < size && y + i < size; i++) {
			if (flag) {
				if (map[x + i][y + i] == 0) {
					map[x + i][y + i] = depth;
				}
			} else {
				if (map[x + i][y + i] == depth) {
					map[x + i][y + i] = 0;
				}
			}
		}
	}
	
	private static void print() {
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println("--------------");
	}
}

 

개선한 현재 코드

import java.util.Scanner;

public class Main {
	
	static int N, map[][], count = 0;
	
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		N = s.nextInt();
		map = new int[N][N];
		
		findStart();
		System.out.println(count);
	}

	private static void findStart() {
		for (int j = 0; j < N; j++) {
			visitCheck(0, j, 1);
			backTracking(1);
			visitCheck(0, j, -1);
		}
	}

	private static void backTracking(int depth) {
		if (depth == N) {
			count++;
			return;
		}
		
		for (int j = 0; j < N; j++) {
			if (map[depth][j] == 0) {
				visitCheck(depth, j, 1);
				backTracking(depth + 1);
				visitCheck(depth, j, -1);
			}
		}
	}

	private static void visitCheck(int x, int y, int val) {
		for (int i = 0; i < N; i++) {
			map[i][y] += val;
			map[x][i] += val;
			
			if (x - i >= 0 && y - i >= 0)
				map[x - i][y - i] += val;
			
			if (x - i >= 0 && y + i < N)
				map[x - i][y + i] += val;	
			
			if (x + i < N && y - i >= 0)
				map[x + i][y - i] += val;
			
			if (x + i < N && y + i < N)
				map[x + i][y + i] += val;
		}
	}
}

int형이라 그런지 시간은 더 오래걸린다..

 

아이디어가 중요한 문제같다. 처음엔 스트레스 받았지만 재밌게 풀었음

끝!