[백준 260] DFS와 BFS

🍎 [백준 1260] DFS와 BFS

문제 링크

⚾ 코드

    from collections import deque

    # 정점의 개수 N(1 ≤ N ≤ 1,000)
    # 간선의 개수 M(1 ≤ M ≤ 10,000)
    # 탐색을 시작할 정점의 번호 V
    N, M, V = map(int, input().split())

    graph = [[] for _ in range(N+1)]
    visited = [False]*(N+1)

    for _ in range(M):
        a, b = map(int, input().split())
        # 양방향이기 때문에 리스트 두 군데 다 추가해주어야 한다.
        graph[a].append(b)
        graph[b].append(a)

    # 인접 리스트를 사용할 것이기 때문에 정렬이 필요함.
    for i in range(N+1):
        graph[i].sort()

    # dfs 구현

    def dfs(node):
        if visited[node] == False:
            # 아직 방문하지 않았을 경우
            visited[node] = True
            # 방문 기록 해주고
            print(node, end=" ")
            # 인접한 노드에서 다시 dfs 호출
            for i in range(len(graph[node])):
                dfs(graph[node][i])

    # bfs를 위한 deque
    q = deque()

    def bfs(node):
        if visited[node] == True:
            # 아직 방문하지 않았을 경우
            # dfs를 먼저 구현했기 때문에 visited는 True로 초기화 되어 있을 것
            # 따라서 True가 방문하지 않았을 경우이다.
            visited[node] = False
            # 방문 기록을 해준 후
            q.append(node)
            # q에 삽입해준다.
            print(node, end=" ")
            while q:
                # q가 비었을 때 까지 반복
                x = q.popleft()
                # 맨 앞에서 하나 꺼낸 후 인접한 모든 노드들을 방문하고 q에 append
                for i in graph[x]:
                    if visited[i] == True:
                        visited[i] = False
                        print(i,  end=" ")
                        q.append(i)

    dfs(V)
    print()
    bfs(V)

🔔 해결과정 & 깨달은 점

• dfs와 bfs의 기본 아이디어를 구현해보았다.
• 양방향 간선일 경우 양쪽에 다 추가해 주어야 한다.
• 인접 리스트의 경우 정렬을 해주어야 가장 숫자가 작은 노드부터 방문할 수 있었다.
• dfs는 이제 잘 구현하는 것 같은데, bfs를 작성할 때 시간이 조금 걸렸다. bfs도 익숙해 질 수 있도록 노력하자.