[BOJ] Python, Ruby 백준 N-Queen(9663)

 

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

 

N-Queen 유명한 완전탐색 백트래킹 문제이다.

N * N 체스판에 N개의 퀸이 서로 잡지 못하는 상태로 위치할 수 있는 모든 경우의 수를 찾는 문제이다.

 

풀이.

퀸은 왼쪽 대각선, 오른쪽 대각선, 상, 하, 좌, 우의 이동이 가능하다.

즉.

1. 상, 하, 좌, 우

2. 왼쪽 대각선

3. 오른쪽 대각선

을 판별하는 방문 배열을 만들면 된다.

 

만약 좌표가 x,y라고 한다면,  

상, 하, 좌, 우는 어디를 이동하던 늘 x, y중 하나가 타켓점과 같다.(배열 그대로의 값을 사용하면 됌)

 

왼쪽 대각선은 어디를 이동하던 늘  x + y를 더한 값이 타켓점의 x + y한 값과 같다. (n[행을 의미] + i[열을 의미])

 

오른쪽 대각선은 어디를 이동하던 늘  x - y를 더한 값이 타켓점의 x - y한 값과 같다. (n[행을 의미] - i[열을 의미])

 

위와 같이 한다면, 퀸의 이동 동선에 겹치지 않는 선에서 퀸을 놓을 수 있는 경우의 수를 구할 수 있게 된다.

 

 

import sys
input = sys.stdin.readline

N = int(input())

def dfs(n): # n은 깊이이자 x 좌표
    global result
    if n == N: # x값이 체스판 끝까지 도달했을때 경우의 수 증가
        result += 1
        return
	# for문이 다 돌아도 dfs를 들어가지 못하면 x(n) 값이 증가하지 않는 상태로 탐색하지 않고 리턴
    for i in range(N):
        if visited1[i] == visited2[n-i] == visited3[n+i] == 0:
            visited1[i], visited2[n - i], visited3[n + i] = 1,1,1
            dfs(n+1)
            visited1[i], visited2[n - i], visited3[n + i] = 0, 0, 0


visited1 = [0] * N
visited2 = [0] * (2*N)
visited3 = [0] * (2*N)
result = 0
dfs(0)
print(result)

 

 

 

 

# frozen_string_literal: true
N = gets.to_i
visited1 = Array.new(N,0)
visited2 = Array.new(2*N, 0)
visited3 = Array.new(2*N, 0)

def dfs(n,visited1,visited2,visited3)
  if n == N
    $result += 1
    return
  end

  (0...N).each do |i|
    if visited1[i] == visited2[n-i] && visited2[n-i] == visited3[n+i] && visited3[n+i] == 0
      visited1[i],visited2[n-i], visited3[n+i]= 1,1,1
      dfs(n+1,visited1,visited2,visited3)
      visited1[i],visited2[n-i], visited3[n+i]= 0,0,0
    end
  end
end

$result = 0
dfs(0,visited1,visited2,visited3)
puts "#{$result}"

 

회고,

아직 세계관 확장하는 주관이 잡히지 않은듯하다. 좀 더 많은 백트래킹 문제를 접해봐야 겠다,,