[코딩테스트] 1260번 DFS와 BFS

내 코드

N, M, V = map(int, input().split(' '))


def dfs(graph, start, visited, order):
    visited[start] = True
    order.append(start)

    for e in graph[start]:
        if not visited[e]:
            dfs(graph, e, visited, order)


def bfs(graph, start, visited, order):
    queue = [start]

    while queue:
        item = queue.pop(0)
        if not visited[item]:
            visited[item] = True
            order.append(item)
            queue.extend(graph[item])


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

for _ in range(M):
    A, B = map(int, input().split(' '))
    graph[A].append(B)
    graph[B].append(A)

visited = [False] * (N + 1)
order = []
dfs(graph, V, visited, order)
print(' '.join(map(str, order)))

visited = [False] * (N + 1)
order = []
bfs(graph, V, visited, order)
print(' '.join(map(str, order)))

 

 

 

chatGPT 개선 문의

코드가 전반적으로 잘 작성되었습니다. DFS와 BFS 모두 정상적으로 작동하며, 간단하고 깔끔한 방식으로 구현되어 있습니다. 다만, 몇 가지 개선 사항을 제안해 볼 수 있습니다.

개선 사항

1. 간선 정렬: 문제에서 언급된 것처럼 정점 번호가 작은 순서대로 방문해야 하므로, graph에 간선을 추가한 후, 각 리스트를 정렬해주는 것이 필요합니다. 입력된 간선은 순서가 보장되지 않기 때문에, 정렬하지 않으면 원하는 결과가 나오지 않을 수 있습니다.

for neighbors in graph:
    neighbors.sort()

 

2. BFS에서 deque 사용: queue의 pop(0)은 리스트의 첫 번째 요소를 제거하면서 모든 요소를 앞으로 이동시키기 때문에 시간 복잡도가 O(N)입니다. 대신, collections.deque를 사용하여 O(1)로 popleft()할 수 있습니다.

from collections import deque

def bfs(graph, start, visited, order):
    queue = deque([start])
    while queue:
        item = queue.popleft()
        if not visited[item]:
            visited[item] = True
            order.append(item)
            queue.extend(graph[item])

 

3. visited 초기화 및 결과 출력 코드 개선: visited와 order 변수를 초기화하는 부분이 중복되므로, 이를 함수로 만들어 간단하게 만들 수 있습니다.

def reset_visited_and_order(n):
    return [False] * (n + 1), []

visited, order = reset_visited_and_order(N)
dfs(graph, V, visited, order)
print(' '.join(map(str, order)))

visited, order = reset_visited_and_order(N)
bfs(graph, V, visited, order)
print(' '.join(map(str, order)))

 

4. 코드 전체: 위의 개선 사항을 반영한 코드는 아래와 같습니다.

from collections import deque

def dfs(graph, start, visited, order):
    visited[start] = True
    order.append(start)
    for e in graph[start]:
        if not visited[e]:
            dfs(graph, e, visited, order)

def bfs(graph, start, visited, order):
    queue = deque([start])
    while queue:
        item = queue.popleft()
        if not visited[item]:
            visited[item] = True
            order.append(item)
            queue.extend(graph[item])

def reset_visited_and_order(n):
    return [False] * (n + 1), []

N, M, V = map(int, input().split())
graph = [[] for _ in range(N + 1)]

for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)
    graph[B].append(A)

for neighbors in graph:
    neighbors.sort()

visited, order = reset_visited_and_order(N)
dfs(graph, V, visited, order)
print(' '.join(map(str, order)))

visited, order = reset_visited_and_order(N)
bfs(graph, V, visited, order)
print(' '.join(map(str, order)))

 

요약

 

• 간선 정렬로 올바른 탐색 순서 보장
• BFS에 deque 사용으로 성능 개선
• visited 초기화 코드 리팩토링

 

 

 

내 생각 정리

• def 를 위로 올리고, input() 부분을 아래로 위치하는 걸로 통일해야겠다.
• queue 사용할때 성능 개선을 위해 deque를 써야겠다.
• 중복 코드는 함수로 묶어야겠다.