21.04.14 알고리즘 공부 24일차 (백트래킹)

1.  N-Queen

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1 복사

8

예제 출력 1 복사

92

 

---

해결 방법 : 백트래킹

 

이유 : 

백트래킹은 전체적으로 DFS를 하는 부분 + 문제별로 제한사항을 두는 코드 이렇게 두개를 짜는듯. 결국 DFS는 코드는 비슷하고 제한사항을 어떻게 할지는 노가다 조금만 해봐도 가능할듯. 아직 재귀가 부족해서 시간은 오래걸렸음

 

 

참고 자료 : claude-u.tistory.com/245

#196 백준 파이썬 [9663] N-Queen

 

 

문제 : 

www.acmicpc.net/problem/9663

 

def adjacent(x):
    for i in range(x):
        if row[x] == row[i] or abs(row[x] - row[i]) == x - i:
            return False
    return True
        
        
#한줄씩 재귀하며 DFS를 실행
def dfs(x):
    global result
    
    if x == N:
        result += 1

    else:
        for i in range(N):
            row[x] = i
            if adjacent(x):
                dfs(x + 1)

N = int(input())
row = [0] * N
result = 0
dfs(0)
print(result)

 

---