[Java] 백준 9663 N-Queen - 골드4

 

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

9663번: N-Queen

 

체스를 안한 지 오래돼서 퀸이 갈 수 있는 곳이 기억안났음. 구글링 해봤다

딱히 규칙이 보이지 않음.

visit배열과 백트래킹을 사용해야겠다고 생각함.

 

1. 1행의 모든 칸에 대해 퀸이 놓였다고 생각하고 다음 놓을 수 있는 자리에 퀸을 놓기 (visit = true)
2. 퀸이 놓인 행은 올킬이니까 다음 행부터 빠르게 찾기(가지치기)
3. 행마다 한 개씩 안놓이면 N개의 queen을 놓을 수 없음 -> 가지치기

 

 

풀이

public class Main {
  static int result = 0;
  static boolean[][] isQueen;

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

    isQueen = new boolean[N][N];
    dfs(0);

    System.out.println(result);
  }

  private static void dfs(int row) {
    for (int i =0; i<isQueen[0].length; i++) {
      if (canLay(row, i)) {
        if (row == isQueen.length-1) {
          result++;
          continue;
        }
        isQueen[row][i] = true;
        dfs(row+1);
        isQueen[row][i] = false;
      }
    }
  }

  private static boolean canLay(int row, int col) {

    int tmpR = row-1;
    int tmpC = col-1;
    while (0 <= tmpR && 0 <= tmpC) {
      if (isQueen[tmpR][tmpC])
        return false;
      tmpR--; tmpC--;
    }

    tmpR = row-1;
    tmpC = col+1;
    while (0 <= tmpR && tmpC < isQueen.length) {
      if (isQueen[tmpR][tmpC])
        return false;
      tmpR--; tmpC++;
    }

    for (int i = row-1; i >= 0; i--) {
      if (isQueen[i][col])
        return false;
    }

    return true;
  }
}

• queen이 놓인 자리에는 isQueen배열을 true로 만들어줌
• 0행부터 N-1행까지 하나씩 queen의 자리를 찾음
  • 놓일 수 있는 자리인지 확인하는 canLay함수를 구현
  • 왼쪽 위/위/오른쪽 위 만 queen이 있는지 확인한다 (어차피 한 행씩 내려가면서 queen을 놓고 있으니 아래에는 queen이 없다)
• 놓을 수 없다면 다음행이 실행되지 않음
• 만약 가장 마지막 행에 queen을 놓았다면 result에 1을 증가시켜줌

 

 

+) queen을 놓고 다음 queen이 들어갈 수 없는 자리를 표시하려 했지만 메모리 초과가 난다