[N-Queen][Python] 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# BackTracking : Stack to store data, Recursion
def nqueen(result, N):
    global count
    if len(result) == N: # 정답 배열(result)의 길이가 N과 같아지면 result 을 프린트한다.
        count += 1
        print(count, result)
        return 0
    candidate = list(range(N)) # 0 부터 N-1 까지로 구성된 후보군(cadidate) 배열을 만든다.


    for i in range(len(result)): # 처음엔 [i] 만큼만. 이후 점점 한개씩 늘어난다.

        # 제외할 것 제외하고 이후 24번 줄에서 후보군 체크
        if result[i] in candidate: # 같은 열에 놓이는지 체크
            candidate.remove(result[i]) # 같은 열에 놓이면 후보군에서 제외

        distance = len(result) - i

        if result[i] + distance in candidate: # 같은 대각선 상에 놓이는지 체크
            candidate.remove(result[i] + distance) # 같은 대각선 상에 놓이면 후보군에서 제외
        if result[i] - distance in candidate: # 같은 대각선 상에 놓이는지 체크
            candidate.remove(result[i] - distance) # 같은 대각선 상에 놓이면 후보군에서 제외

    # 후보군 체크
    if candidate != []:
        for i in candidate:
            result.append(i) # 후보군의 요소를 정답 배열의 i+1 번째 요소로 설정
            nqueen(result, N) # 재귀적으로 다음 후보군 체크
            result.pop()
    else:
        return 0

count = 0
num = int(input("Input N : "))
for i in range(num):
    nqueen([i], num)
if count == 0:
    print("No solution")



# # BackTracking : Recursion
# def solve(idx):
#     global n
#     if idx == n:
#         return 1
#     ret = 0
#
#     for i in range(n):
#         selected[idx] = i
#         if isNQueen(idx):
#             ret += solve(idx+1)
#
#     return ret
#
# def isNQueen(idx):
#     for i in range(idx):
#         if selected[i] == selected[idx] or abs(idx-i) == abs(selected[idx]-selected[i]):
#             return False
#     return True
#
# for t in range(int(input())):
#     n = int(input())
#     selected = [0] * n
#     print("#{} {}".format(t+1, solve(0)))

댓글

댓글 쓰기

이 블로그의 인기 게시물

[python]섬의 둘레구하기

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 direction = (( - 1 , 0 ), ( 1 , 0 ), ( 0 , - 1 ), ( 0 , 1 )) def sol (st_y, st_x): global w, h cnt = 0 for d in direction: next_y = st_y + d[ 0 ] next_x = st_x + d[ 1 ] if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w or MAP[next_y][next_x] == 0 : cnt += 1 return cnt while True: w, h = map(int, input() . split()) if (w, h) == ( 0 , 0 ): break MAP = [list(map(int, input() . split())) for _ in range(h)] answer = 0 for i in range(h): for j in range(w): if MAP[i][j] == 0 : continue answer += sol(i,j) print (answer) 아이디어는 단순하다. 모든 좌표를 순회하면서 주변이 땅으로 연결되지 않을때 cnt를 하나씩 증가시킨다.
자세한 내용 보기

백트래킹으로 부분집합구하기(Get Powerset usiing Backtracking)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 def backtrack (a, k, input): global MAXCANDIDATES c = [ 0 ] * MAXCANDIDATES if k == input: process_solution(a,k) #답이면 원하는 작업한다. else : k += 1 ncandidates = construct_candidates(a,k,input,c) for i in range(ncandidates): a[k] = c[i] backtrack(a, k, input) def process_solution (a, k): print ( "(" , end = "" ) for i in range(k + 1 ): if a[i]: print (i, end = " " ) print ( ")" ) #후보군 구하는 함수 def construct_candidates (a, k, input, c): c[ 0 ] = True c[ 1 ] = False return 2 #Main MAXCANDIDATES = 100 NMAX = 100 a = [ 0 ] * NMAX backtrack(a, 0 , 3 )
자세한 내용 보기

[패턴매칭][Python]보이어 무어 알고리즘

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 # 보이어 무어 알고리즘 for t in range(int(input())): pattern = input() text = input() pivot = len(pattern) - 1 skip_array = list(pattern) skip_array . reverse() result = 0 while result != 1 and pivot < len(text): if pattern[len(pattern) - 1 ] != text[pivot]: if text[pivot] in skip_array: nums = skip_array . index(text[pivot]) pivot += nums else : pivot += len(pattern) else : for i, j in zip(range(pivot, pivot - len(pattern), - 1 ), skip_array): if text[i] == j: result = 1 else : result = 0 pivot = i break print ( "#{} {}" . format(t + 1 , result)) 참고문제: SW Expert Academy 4864번 문제
자세한 내용 보기