• 문제
  • 1697번: 숨바꼭질
• 해설

  • import sys
    from collections import deque
    
    sys.setrecursionlimit(1000000)
    
    subin, sister = [*map(int, sys.stdin.readline().strip().split())]
    
    # 시작부터 수빈이가 선두인 경우는 수빈이가 뒷걸음치는 것만 가능
    if subin >= sister:
        print(subin - sister)
        sys.exit()
    
    q = deque()
    map_ = [0] * 200000
    
    
    def bfs(subin_position, current_seconds):
        candidates = [subin_position - 1, subin_position + 1, 2 * subin_position]
        candidates = [candidate for candidate in candidates
                      if 0 <= candidate <= 100000 and map_[candidate] == 0]
        next_seconds = current_seconds + 1
        for candidate in candidates:
            # 수빈이가 동생 찾았을 때
            if candidate == sister:
                print(next_seconds)
                sys.exit()
    
            map_[candidate] = next_seconds
    
            q.appendleft((candidate, next_seconds))
        if len(q):
            bfs(*q.pop())
    
    
    bfs(subin, 0)

• 포인트
  • 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를 구현