[Python][DFS]최장경로 

 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
66
67
68
69
70
def recur():
    global n
    if len(candidate) == n:
        l = candidate[:]
        result.append(l)
    else:
        for i in [0, 1]:
            candidate.append(i)
            recur()
            candidate.pop()

def sol():
    global n, k, answer
    for i in range(1 << n):
        tmp = 0
        for j in range(n):
            if i & (1 << j):
                tmp += a[j]
                print(a[j], end=" ")
        print()
        if tmp == k:
            answer += 1

def convert():
    global n
    for i in result:
        tmp = []
        for j in range(n):
            c = a[j] * i[j]
            tmp.append(c)
        aa.append(tmp)

for t in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    aa = list()
    result = []
    candidate = []


    answer = 0
    recur()
    tt = []
    for i in result:
        tmp = 0
        for j in range(n):
            if i[j] == 1:
                tmp += a[j]
        if tmp == k:
            tt.append(i)
            answer += 1
    print(tt)
    print("#{} {}".format(t+1, answer))

    print('-' * 50)
    answer = 0
    convert()
    print(aa)
    for i in aa:
        if sum(i) == k:
            answer += 1
    print("#{} {}".format(t + 1, answer))




    print('-'*50)
    answer = 0
    sol()
    print("#{} {}".format(t+1, answer))

댓글

댓글 쓰기

이 블로그의 인기 게시물

[DFS][Queue][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 class position (): def __init__ (self, x, y, dist): self . x = x self . y = y self . dist = dist def bfs (x, y, dist): global result queue . append(position(x, y, dist)) visit[y][x] = True while queue: current = queue . pop( 0 ) if current . x == end[ 0 ] and current . y == end[ 1 ]: result = current . dist - 2 break for i in range( 4 ): next_y = current . y + direction[i][ 0 ] next_x = current . x + direction[i][ 1 ] next_dist = current . dist + 1 if next_x >= 0 and next_y >= 0 and next_x < width and next_y < height: if visit[next_y][next_x] == False and maze[next_y][next_x] == 0 or ...
자세한 내용 보기

[Recursive][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 def check (a, b, card): if card[a] is card[b]: return a if card[a] is 1 : if card[b] is 2 : return b else : return a elif card[a] is 2 : if card[b] is 3 : return b else : return a else : if card[b] is 1 : return b else : return a def rec (st, ed, card): if st is ed: return st l = rec(st, (st + ed) // 2 , card) r = rec((st + ed) // 2 + 1 , ed, card) return check(l, r, card) def main (): T = int(input()) for tc in range( 1 , T + 1 ): N = int(input()) card = list(map(int, input() . split())) print ( "#{} {}" . format(tc, rec( 0 , N - 1 , card) + 1 )) main() 4880. [파이썬 S/W 문제해결 기본] 5일차 - 토너...
자세한 내용 보기

[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를 하나씩 증가시킨다.
자세한 내용 보기