[백준][1260] DFS와 BFS

1260 DFS와BFS

• 문제
  • 1260번: DFS와 BFS (acmicpc.net)
• 해설

  • import sys
    import queue
    
    sys.setrecursionlimit(99999)
    
    vertex_count, edge_count, start_vertex = [int(x) for x in sys.stdin.readline().strip().split()]
    edges = [list(map(int, x.strip().split())) for x in sys.stdin.readlines()]
    
    adj_dict = dict()
    chk_dict = dict()
    
    for edge in edges:
        vertex_1, vertex_2 = edge
        if vertex_1 not in adj_dict:
            adj_dict[vertex_1] = [vertex_2]
        else:
            adj_dict[vertex_1].append(vertex_2)
        if vertex_2 not in adj_dict:
            adj_dict[vertex_2] = [vertex_1]
        else:
            adj_dict[vertex_2].append(vertex_1)
    
    for vertex in adj_dict:
        chk_dict[vertex] = False
        adj_dict[vertex] = sorted(list(set(adj_dict[vertex])))
    
    sorted_vertex = sorted(list(chk_dict.keys()))
    chk_dict_bfs = chk_dict.copy()
    dfs_ans = []
    bfs_ans = []
    queue_for_bfs = queue.Queue()
    
    
    def dfs(vertex):
        chk_dict[vertex] = True
        dfs_ans.append(vertex)
        for k in adj_dict[vertex]:
            if not chk_dict[k]:
                dfs(k)
    
    
    def bfs(vertex):
        chk_dict_bfs[vertex] = True
        bfs_ans.append(vertex)
        for k in adj_dict[vertex]:
            if not chk_dict_bfs[k]:
                chk_dict_bfs[k] = True
                queue_for_bfs.put(k)
        if queue_for_bfs.qsize():
            bfs(queue_for_bfs.get())
    
    
    if start_vertex in adj_dict.keys():
        dfs(start_vertex)
        bfs(start_vertex)
        print(' '.join([str(x) for x in dfs_ans]))
        print(' '.join([str(x) for x in bfs_ans]))
    else:
        print(start_vertex)
        print(start_vertex)

• 포인트
  • BFS와 DFS를 구현