백준 BFS/DFS 문제입니다. 알고리즘 숙달을 위한 문제 반복풀이입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.
문제
https://www.acmicpc.net/problem/1260
[나의 풀이1]
⌛ 시간 초과
양방향 그래프 구현이 어려워 해답을 참고하여 구현하였습니다.
def dfs(v):
# 순회한 정점 print
print(v,end=" ")
for i in graph[v]:
if not visitied[i]:
visitied[i] = True
# DFS 구현을 위한 재귀함수
dfs(i)
def bfs(v):
# queue 활용 bfs 구현
from collections import deque
queue = deque([v])
while queue:
v = queue.pop()
print(v,end=" ")
for i in graph[v]:
if not visitied[i]:
visitied[i] = True
queue.appendleft(i)
N, M, V = map(int, input().split())
# 그래프 구현
graph = [[] for _ in range(N+1)]
visitied = [False]*(N+1)
# 양방향이기 때문에 연결된 양쪽 정점 모두 append
for _ in range(M):
a, b = map(int,input().split())
graph[a].append(b)
graph[b].append(a)
# 작은 값을 우선으로 돌기 때문에 sort()
for i in range(N+1):
graph[i].sort()
# 첫 순회 위치 = True
visitied[V] = True
dfs(V)
print()
# visitied list 초기화
for i in range(N+1):
visitied[i] = False
visitied[V] = True
bfs(V)
양방향 그래프 탐색 구현을 위해 연결된 양쪽 정점 모두 서로의 값을 추가해주는 것이 포인트였습니다. 재귀함수를 통한 DFS 구현과 queue 구조를 활용하여 BFS를 구현하였습니다.
[나의 풀이2]
⌛ 이전 풀이
from collections import deque
def getData():
N, M, V = list(map(int,input().split()))
graph = [set()for i in range(N+1)]
for _ in range(1,M+1): # i= 1~5
connect = list(map(int,input().split()))
graph[connect[0]].add(connect[1])
graph[connect[1]].add(connect[0])
return graph,V
graph,V = getData()
print(graph)
def DFS(graph,V):
DFS_visited = []
stack = [V]
while stack:
n = stack.pop()
if n not in DFS_visited:
DFS_visited.append(n)
stack += sorted(list(graph[n] - set(DFS_visited)),reverse=True)
return DFS_visited
DFS_visited = DFS(graph,V)
def BFS(graph,V):
BFS_visited = []
queue = deque([V])
while queue:
n = queue.popleft()
if n not in BFS_visited:
BFS_visited.append(n)
queue += sorted(graph[n] - set(BFS_visited))
return BFS_visited
BFS_visited = BFS(graph,V)
print(*DFS_visited)
print(*BFS_visited)
DFS, BFS 구현 구조는 유사하지만 다음에 방문할 정점들(graph[n])에 set()형태로 바꾸어준 방문한 정점들(visited)를 빼주는 방식으로 방문하지 않은 정점들만 stack(DFS) or queue(BFS) 구조에 더해주는 방식입니다.
감사합니다.