⛹️ 라이프/2020 겨울방학 모각코(개인)

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

고도고도 2020. 12. 23. 23:00

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

Contribute to k906506/2020_Winter_Assemble-And-selfcode development by creating an account on GitHub.

github.com