오늘 진행한 일들
- 알고리즘 강의 시청
- 알고리즘 코드 문제 풀이
알고리즘 문제
그동안 DFS와 익숙해질려고 문제에 DFS를 사용해 보았는데 이번에는 문제를 통해서 BFS도 사용해 보았다.
바이러스(from 백준)
- 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성한다
- 방문할 수 있는 정점이 여러 개인 경우, 정점 번호가 작은 것을 먼저 방문한다
- 첫째 줄에 DFS를 수행한 결과를 출력하고 둘째 줄에 BFS를 수행한 결과를 출력한다
- V부터 방문된 점을 순서대로 출력한다
작성한 코드
그래프 초기화 및 구성
graph = defaultdict(list)
for _ in range(M):
x, y = map(int, sys.stdin.readline().split())
graph[x].append(y)
graph[y].append(x)
for key in graph:
graph[key].sort()graph는 defaultdict(list)로 초기화되어, 각 정점에 연결된 정점들을 리스트로 저장한다. 각 간선 정보를 입력받아 그래프에 추가한다. 양방향 그래프이므로
x와 y를 서로의 리스트에 추가한다. 방문할 수 있는 정점이 여러 개인 경우, 정점 번호가 작은 것을 먼저 방문하도록 각 정점의 인접 리스트를 정렬한다.
DFS 함수 정의
def dfs(graph, start, visited):
stack = [start]
result = []
while stack:
v = stack.pop()
if not visited[v]:
visited[v] = True
result.append(v)
stack.extend(sorted(graph[v], reverse=True))
return resultdfs 함수는 스택을 사용하여 DFS를 구현한다. 스택 초기화는 시작 정점을 스택에 넣는다. 탐색 루프는 스택이 빌 때까지 반복한다. 스택에서 정점을 꺼내 방문 여부를 확인한다. 방문하지 않은 경우, 방문을 기록하고 결과 리스트에 추가한다. 인접 정점들을 역순으로 스택에 추가하여 정점 번호가 작은 것을 먼저 방문하도록 한다.
BFS 함수 정의
def bfs(graph, start):
queue = deque([start])
visited = defaultdict(bool)
visited[start] = True
result = []
while queue:
v = queue.popleft()
result.append(v)
for neighbor in sorted(graph[v]):
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor)
return resultbfs 함수는 큐를 사용하여 BFS를 구현한다. 큐 초기화는 시작 정점을 큐에 넣는다. 탐색 루프는 큐가 빌 때까지 반복한다. 큐에서 정점을 꺼내 결과 리스트에 추가한다. 인접 정점들을 정렬하여 큐에 추가하여 정점 번호가 작은 것을 먼저 방문하도록 한다.
방문 배열 초기화 및 탐색 수행
visited_dfs = defaultdict(bool)
visited_bfs = defaultdict(bool)
dfs_result = dfs(graph, V, visited_dfs)
bfs_result = bfs(graph, V)
print(' '.join(map(str, dfs_result)))
print(' '.join(map(str, bfs_result)))visited_dfs와 visited_bfs는 각각 DFS와 BFS 탐색에서 각 정점의 방문 여부를 기록하는 배열이다. dfs 함수를 호출하여 DFS 탐색 결과를 dfs_result에 저장한다. bfs 함수를 호출하여 BFS 탐색 결과를 bfs_result에 저장한다. 각각의 결과를 공백으로 구분하여 출력한다.
