[백준] 단계별로 풀어보기(단계:14,백트래킹,JAVA)9663번, N-Queen

문제 링크

9663번: N-Queen

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

백트래킹이란 깊이 우선 탐색을 바탕으로 탐색 중 오답을 만나면 이전 분기점으로 돌아가서 다른 해결방법이 있는지 확인하고 더 이상 없으면 더 이전에 분기점으로 돌아가서 해결방법을 찾아보는 방식입니다.깊이 우선 탐색은 모든 경우의 수를 검색하게 되지만 백트래킹은 오답으로 판단될시 그에 해당하는 자식 노드들은 모두 무시하고 넘어가기 때문에 더욱 효율적으로 코드가 진행됩니다.

검은색 : 실행되지 않은 노드

빨간색 : 오답으로 판단한 노드

초록색 : 올바른 값이라고 판단한 노드

위에 그림처럼 부모노드가 틀리다고 판정되면 자식노드 무시하고 이전 분기점으로 돌아가서 확인하는 방식으로 코드가 전개되어 가는 방식입니다.

체스의 말 : 퀸(Queen)퀸은 좌/우/상/하 및 대각선을 모두 이동할수 있는 말입니다.

사진출처 : https://ko.wikipedia.org/wiki/%ED%80%B8_(%EC%B2%B4%EC%8A%A4)

체스판 크기가 4일때 퀸이 놓일 수 있는 경우 중 하나를 설명하도록 하겠습니다.

체스판에 첫 번째 열부터 퀸을 놓는 형식을 사용하였습니다.

첫 번째 열

두 번째 열

세 번째 열

네 번째 열

 

처음 이 문제에 접근할 때 boolean형식의 2차원 배열을 체스판처럼 인식하여 false이면 퀸을 놓을 수 있는 구역이고 true이면 놓을 수 없는 구역으로 나누어서 진행하려고 했습니다.

이 알고리즘을 backTracking으로 구현하니 체스판에 관련한 boolean형의 2차원 배열을 지속적으로 초기화하고 이전 노드일 때 배열을 가져오는 것이 비효율적이라고 생각하게 되었습니다. 그래서 다른 방법이 있는지 혼자 생각하다 도저히 떠오르지 않아 구글링하여 위키백과에서 1차원 배열을 이용하는 방법을 보고 알고리즘을 작성하였습니다. 

1차원 배열의 값들을 하나의 열에 퀸이 놓인 위치로 생각하여 알고리즘을 작성하였습니다.

위에 네 번째 열일 때 배열은 {1, 3, 0, 2} 되어있어야 합니다.

퀸의 위치를 놓일 수 있는지 확인할 때 대각선에 퀸에 위치가 존재하는지 확인하는 알고리즘을 만들때 가장 힘들었습니다.

퀸이 놓인 위치를 (0,1)의 좌표라고 생각하고 대각선 좌표는 (1,0) , (1,2) , (2,3)이 존재합니다.

여러가지 연산을 시도해보니 x좌표끼리 빼고 y좌표끼리 빼고 절대값으로 표현하여 같은지 확인해보았는데 같으면 대각선에 위치한다는 것을 알게되어 알고리즘으로 작성하였습니다.

예를들어 (1,0)비교할 때에 x좌표 : |0-1| = 1  y좌표 : |1-0| = 1로 같아집니다.

대각선이 아닌 좌표(1,3)를 비교할 때에는 x좌표 : |0-1| = 0 y좌표 : |1-3|로 값이 다르기 때문에 대각선에 존재하지 않습니다.

• 체스판에 열마다 존재하는 퀸의 위치를 저장할 배열 chess을 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• 퀸이 놓일 수 있는 경우의 수를 구하는 함수 queen을 만들었습니다.
• 퀸이 놓일 수 있는지 확인하는 함수 check를 만들었습니다.
• System.out.println()을 사용하여 result를 출력하였습니다.

• current는 현재 몇 번째 열인지 나타내는 수입니다.
• check함수를 통해 퀸이 놓일 수 있는 지 확인하고 놓일 수 있다면 다음 열로 넘어가며 backTracking을 하였습니다.
• current의 값이 길이 size와 동일하면 모든 퀸이 배치된 것으로 result값을 +1 해주었습니다.

결과 코드

import java.io.*;
public class Main{
	static int[] chess;		//체스판 열 기준 배열
	static int size, result=0;	//체스판 사이즈, 결과
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
        //----------입력값 저장 및 배열 초기화, 함수 실행--------
    	size = Integer.parseInt(br.readLine());
    	chess = new int[size];
    	queen(0);
    	System.out.println(result);	//결과 출력
    	br.close();
	}
	public static void queen(int current) {
    //-------------퀸의 개수가 사이즈와 같을 때------------
		if(current==size) {
			result++;
			return;
		}
   //---------backTracking으로 퀸의 자리 저장------------
		for(int i=0;i<size;i++) {
			chess[current] = i;
			if(check(current))
				queen(current+1);
		}
	}
	public static boolean check(int n) {
  //------------queen 자리 조건-----------------
		for(int i=0;i<n;i++) {
  //----------------같은 행/열에 퀸이 존재할 경우------------
			if(chess[i]==chess[n])
				return false;
//----------------대각선에 퀸이 존재할 경우------------
			else if(Math.abs(n-i)==Math.abs(chess[n]-chess[i]))
				return false;
		}
		return true;
	}
}