국가직 7급 시험 1달 전, 자료구조 문제 하나 풀어 봄!

[홍재연]

문제의 정답은 무엇이고

왜? 정답인지? 설명해 보세요. 댓글로

==========================================

# 깊이우선탐색

def dfs(graph, visited, current):

    visited[current] = True                   #현재노드 방문 처리

    print(current, end = ' ')                  #현재 방문한 노드 출력

    for i in graph[current]:                   #현재노드의 인접노드를 순차적 확인

        if not visited[i]:                          #인접노드 정점 i가 방문되지 않았다면

            dfs(graph, visited, i)             #재귀호출 - 인접노드 재귀적 방문

graph = {                                         #그래프를 인접리스트 형식으로 표현

    1:[2, 3, 4],

    2:[1, 6, 7],

    3:[1, 4, 5],

    4:[1, 3],

    5:[3, 8],

    6:[2, 7],

    7:[2, 6],

    8:[5]

}

visited = [False] * 9                     #노드 방문 처리 리스트

dfs(graph, visited, 1)                   #시작노드는 1번 정점

==========================================

국가직 7급 시험 1달 전입니다.

새로운 것을 더 알려고 공부하는 것보다는

적어도 지금까지 공부한 내용이 출제되었을 때 틀리지 않도록 마무리 정리합니다.

[나너강]

1. While문은 queue.popleft한 정점마다 실행되는데, queue에 들어가는 정점은 시작 정점이거나 방문되지않은(not in + visited)정점이므로 n번 실행
2. 각 인접한 정점을 찾는 과정은 정점에 연결된 간선을 중복없이(not in) 찾는 것과 같으니 연산시간은 O(간선수)
3. 2.의 연장선으로 각 정점에 대한 간선을 중복없이 탐색하는 알고리즘
4. BFS이니 위상정렬에 활용가능

[나너강]

2,3번 알고리즘 다시보니 간선을 중복없이 찾는 것은 아니네요 그래도 수행시간은 O(2e) =O(e)

[블루베타]

4번 위상정렬은 불가능할거라 생각합니다 만약 3번 노드를 방문하기전 {1,2}번 노드를 방문하는게 조건이라면 1번 노드의 인접노드가 {3,4}인 경우 2번 방문전에 3번을 방문하게 됩니다

[블루베타]

다시 보니까 4번에 활용한다는걸 보기 알고리즘을 그대로 사용한다면으로 생각했는데 천천히 읽어보니 2번이 n개의 노드를 각각 방문하는데 O(n) 인접노드를 탐색하는데 O(n)해서 O(n^2)으로 답인거같네요

[홍재연]

제가 추가로 하나 더 질문합니다.

[질문] 그래프를 연결리스트로 표현하면 너비우선탐색 시간은 O(n+e)이다.

1. 올바른 설명?
2. 틀린 설명?

어느 것인가요?

[사사]

무방향 그래프를 인접리스트로 가질때 n개당 2개의 간선을 가지므로 O(n+2e) 상수를 생략하면 방향그래프가 e개의 간선을 같는 O(n+e)와 같네요, 정답 1번 올바른 설명 같습니다.