[Java] SWEA.2808 DFS 백트랙킹

DFS 알고리즘을 사용할 때 연산을 줄이기 위한 함수를 활용한 문제

SWEA.2808

문제 설명

• 체스판과 같이 N*N 크기의 칸이 있을 때 체스 퀸 을 둘 수 있는 위치를 구한다.
• 여기서 둘 수 없는 위치는 '대각선과 수직방향' 에 위치할 땐 둘 수 없다.

풀이 핵심

• N*N 크기의 배열에 놓여있는 체스핀을 1차원 배열에 표현할 것이다.
  예를 들어 (1,3)의 위치에 있는 말은 1차원 배열에서 arr[1] = 3 과 같다.

• 따라서 1차원 배열의 인덱스 값은 체스판의 세로 축이고 배열의 값은 가로축이다.

• 세로 축에 다른 핀이 존재하거나 , 대각선 방향에 다른 핀이 존재하면 안되기에 이를 isPromising 이란 메서드를 통해 핀을 둘 수 있는 위치인지 판별한다.

• 판별한 결과 둘 수 있는 위치이면 DFS를 재귀하고, 안된다면 다음 위치에 시도한다.

• 코드 내 DFS 반복문을 보면 맨 row 가 0 부터 시작하며, 각 row 에서 0번째 열부터 N번째 열까지 차례대로 판별한다.

코드

public class swea_2806 {
	
	static int[] col;
	static int answer;
	static int N;
	
	static private void dfs(int row) {
		if (row == N) {
			answer++;
			return;
		}
		for (int c = 0; c < N; c++) { // 각 Row에서 0번째 열부터 값을 넣어본다.
			col[row] = c; //  (row, c)
			
			if (isPromising(row)) { // 위에서 넣은 값이 맞는지 체크하자
				dfs(row+1); // 맞으면 오케이 다음 행으로 
			}
		}
	}
	
	static boolean isPromising(int currentRow) {
		for (int r = 0; r < currentRow; r++) { 
			// 모든 세로 축 검사
			if (col[r] == col[currentRow]) { // 같은 열에 값이 있으면 실패
				return false;
			}
            // 행의 차와 열의 차가 같으면 대각선이므로 실패
			if(Math.abs(r-currentRow) == Math.abs(col[r]-col[currentRow])) {
				return false;
			}
		}
		return true;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for(int test_case = 1; test_case <= T; test_case++) {
			N = Integer.parseInt(br.readLine());
			
			col = new int[N];
			answer = 0;
			dfs(0);
			
			System.out.println("#" + test_case + " " + answer);
		}
	}

}