[코독하구만 팀] 2020.12.23(수) - 1주차 개인 결과

BFS와 DFS를 개념과 실습 문제를 복습하고 백준 문제를 통해 실제 문제에 적용해봄으로써

둘의 차이와 알고리즘 동작방식에 대해 확실하게 아는 계기가 되었다.

 

1. 이웃 노드 찾기 (그래프 기본)

def main():
    n, m = map(int, input().split())
    node = list(input().split())
    node_dict = dict()

    for i in range(n):
        node_dict[node[i]] = []
    
    for i in range(m):
        srt, dst = input().split()
        if dst not in node_dict[srt]:
            node_dict[srt].append(dst)

    find_node = input()

    print(len(node_dict[find_node]))

if __name__ == "__main__":
    main()

 

 

2. BFS (너비 우선 탐색)

def bfs(node_dict, node):
    visit = []
    queue = []
    queue.append(node)
    while queue:
        element = queue.pop(0)
        if element not in visit:
            visit.append(element)
            queue.extend(node_dict[element])
    return visit

def main():
    n, m = map(int, input().split())
    node = list(input().split())
    node_dict = dict()

    for i in range(n):
        node_dict[node[i]] = []
    
    for i in range(m):
        srt, dst = input().split()
        if dst not in node_dict[srt]:
            node_dict[srt].append(dst)
    
    find_node = input()
    print(*bfs(node_dict, find_node))

if __name__ == "__main__":
    main()

 

 

3. DFS (깊이 우선 탐색)

def dfs(node_dict, node, visit = None):
    if visit is None:
        visit = []
    visit.append(node)
    for element in node_dict[node]:
        if element not in visit:
            dfs(node_dict, element, visit)
    return visit

def main():
    n, m = map(int, input().split())
    node = list(input().split())
    node_dict = dict()

    for i in range(n):
        node_dict[node[i]] = []
    
    for i in range(m):
        srt, dst = input().split()
        if dst not in node_dict[srt]:
            node_dict[srt].append(dst)
    
    find_node = input()
    print(*dfs(node_dict, find_node))

if __name__ == "__main__":
    main()

 

 

4. 1260번 DFS와 BFS

def dfs(node, v, visit = None):
    if visit == None:
        visit = []
    visit.append(v)
    for element in node[v]:
        if element not in visit:
            dfs(node, element, visit)
    return visit

def bfs(node, v):
    visit = []
    queue = []
    queue.append(v)
    while queue:
        element = queue.pop(0)
        if element not in visit:
            visit.append(element)
            queue.extend(node[element])
    return visit

def main():
    n, m, v = map(int, input().split())
    node = dict()

    for i in range(n):
        node[i+1] = []
    
    for i in range(m):
        srt, dst = map(int, input().split())
        if dst not in node[srt]:
            node[srt].append(dst)
        if srt not in node[dst]:
            node[dst].append(srt)

    for i in range(n):
        node[i+1].sort()
    
    print(*dfs(node, v))
    print(*bfs(node, v))

if __name__ == "__main__":
    main()

 

 

양방향 그래프에 주의해야한다.

 

 

 

- 깃허브 -

github.com/k906506/2020_Winter_Assemble-And-selfcode

k906506/2020_Winter_Assemble-And-selfcode