기본 그래프 탐색의 개념과, 어떤 문제에서 사용할지와 알고리즘까지 적어두셔서 정말 유용한 포스팅입니다.
이 포스팅을 참고로 작성하였습니다.
from collections import deque
# 커스텀 예외
class GraphSettingError(Exception):
pass
# 정보 받아 들이기 ---
# map(int, )이용, 리스트 컴프리헨션 이용
n, m, v = map(int, input().split())
if v <= 0 or v > n:
raise GraphSettingError('\'v\' wrong range')
graph = [[] for _ in range(n+1)]
for _ in range(m):
start_node, dest_node = map(int, input().split())
# 노드 숫자가 비정상적일 경우 예외처리
if start_node > n or dest_node > n:
raise GraphSettingError('Node number bigger than n')
# 양방향 간선
graph[start_node].append(dest_node)
graph[dest_node].append(start_node)
# 정점 번호가 더 낮은 순으로 검사하므로, 오름차순으로 정렬해준다.
for i in range(len(graph)):
graph[i].sort()
# dfs bfs 형태 모두 visited를 구현하여 사용해야함
# 스택(리스트)을 활용하여 dfs 출력 ---
visited = [False for i in range(n+1)]
def dfs(graph, v, visited):
# 방문 리스트 값을 True로 바꿈으로써 방문함을 기록
visited[v] = True
print(v, end=' ')
# 방문 정점 v의 간선 정보graph를 확인하여, 연결된 다른 정점 m_v 탐색
# 재귀적으로 탐색하기 때문에, 깊이 탐색을 수행한다.
for m_v in graph[v]:
# print('\n', v,' 에서 진행 중이고,', m_v, '를 탐색하려함')
if not visited[m_v]:
dfs(graph, m_v, visited)
dfs(graph, v, visited)
print(end='\n')
# 큐(deque)를 활용하여 bfs 출력 ---
visited = [False for _ in range(n+1)]
def bfs(graph, v, visit_deque):
queue = deque([v])
visited[v] = True
# queue가 비면 False 반환
while queue:
v = queue.popleft()
print(v, end=' ')
for m_v in graph[v]:
if not visited[m_v]:
queue.append(m_v)
# queue에 올라가는 순간 방문한 것으로 처리. 결국에 queue는 모두 검사하기 때문에 상관없다.
visited[m_v] = True
bfs(graph, v, visited)
더 나은 풀이
파이썬은 대부분 나의 풀이와 비슷한 형태를 보였다. 추가적으로 향상시킬 부분은 같은 값을 가진 visited=[False for _ in range(n+1)]같은 리스트경우 visited = [False] * (n+1)등으로 수정가능하다. 또한 map(int, input().split())을 import sys map(int, sys.stdin.readline().split())으로 효과적으로 성능을 개선시킬 수 있다. sys.stdin.readline().split()을 이용한 성능 개선
리뷰
DFS, BFS는 수 많은 이용 끝에 보편적인 알고리즘이 구현되어 있다. 짧은 시간의 코딩테스트에서 구현을 전부 신경쓸 시간은 없다. 알고리즘을 암기해 두는 것이 현명하다.
