[백준] 1260번 DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1

1 2 4 3
1 2 3 4

예제 입력 2

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2

3 1 2 5 4
3 1 4 2 5

예제 입력 3 복사

1000 1 1000
999 1000

예제 출력 3

1000 999
1000 999

내 코드

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에 간선을 추가한 후, 각 리스트를 정렬해주는 것이 필요합니다. 입력된 간선은 순서가 보장되지 않기 때문에, 정렬하지 않으면 원하는 결과가 나오지 않을 수 있습니다.
2. for neighbors in graph: neighbors.sort()
3. BFS에서 deque 사용: queue의 pop(0)은 리스트의 첫 번째 요소를 제거하면서 모든 요소를 앞으로 이동시키기 때문에 시간 복잡도가 O(N)입니다. 대신, collections.deque를 사용하여 O(1)로 popleft()할 수 있습니다.
4. 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])
5. visited 초기화 및 결과 출력 코드 개선: visited와 order 변수를 초기화하는 부분이 중복되므로, 이를 함수로 만들어 간단하게 만들 수 있습니다.
6. 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)))
7. 코드 전체: 위의 개선 사항을 반영한 코드는 아래와 같습니다.
8. 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 초기화 코드 리팩토링

내 생각

1. 간선 정렬을 해야겠다.
2. queue 사용시 성능 개선을 위해 deque를 써야겠다.
3. 중복 코드는 함수로 묶어야겠다.