[DFS&BFS]그래프 노드의 거리와 경로 

 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
class Node():
    def __init__(self, node, cnt=None):
        self.node = node
        self.cnt = cnt

def dfs(graph, node):
    global result
    visit.append(node)
    # print(node) 방문 노드 출령
    if node == g:
        result = 1
    for i in graph[node]:
        if i not in visit:
            dfs(graph, i)

def bfs(graph, start, cnt):
    global result
    visit.append(start)
    queue = [Node(start, cnt)]
    while queue:
        current = queue.pop(0)
        if current.node == g:
            result = current.cnt
            break
        for i in graph[current.node]:
            if i not in visit:
                new_cnt = current.cnt + 1
                queue.append(Node(i, new_cnt))
                visit.append(i)


for t in range(int(input())):
    graph = dict()
    v, e = list(map(int, input().split()))
    result = 0
    visit = []

    # Graph initialize
    for i in range(v):
        graph[str(i+1)] = []

    # Links allocated by input value
    for _ in range(e):
        key, val = input().split()
        graph[key].append(val)
        graph[val].append(key)

    s, g = input().split()

    # # BFS 문제일 경우
    # bfs(graph, s, 0)

    # DFS 문제일 경우
    dfs(graph, s)

    print("#{} {}".format(t+1, result))
4871. [파이썬 S/W 문제해결 기본] 4일차 - 그래프 경로 (BFS)
5102. [파이썬 S/W 문제해결 기본] 6일차 - 노드의 거리 (DFS)

댓글

  1. q2019년 2월 20일 오전 12:20

    *sample input
    3
    6 5
    1 4
    1 3
    2 3
    2 5
    4 6
    1 6
    7 4
    1 6
    2 3
    2 6
    3 5
    2 5
    9 9
    2 6
    4 7
    5 7
    1 5
    2 9
    3 9
    4 8
    5 3
    7 8
    1 9

    *sample output
    *DFS
    #1 1
    #2 1
    #3 1

    *BFS
    #1 2
    #2 4
    #3 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 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]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 def recur (idx): check[idx] = 1 tmp . append(n[idx]) if len(tmp) == 3 : a = sorted(tmp) if sum(a) not in result: result . append(sum(a)) else : for i in range( 7 ): if check[i] == 0 : recur(i) tmp . pop() check[i] = 0 # def subset(): # for i in range(1<<7): # tmp2 = 0 # cnt = 0 # for j in range(7): # if i & (1<<j): # tmp2 += n[j] # cnt += 1 # if tmp2 not in result and cnt == 3: # result.append(tmp2) for t in range(int(input())): n = list(map(int, input() . split())) result = [] for i in range(len(n)): tmp = [] check = [ 0 ] * 7 recur(i) # subset() res...
자세한 내용 보기