백준 - 그래프(# 1260)
https://www.acmicpc.net/problem/1260
Code 1
import sys
def dfs(v):
print(v, end=' ')
already_visited[v] = 1
for i in range(1,n+1):
if adj_matrix[v][i] == 1 and already_visited[i] == 0:
dfs(i)
def bfs(v):
already_visited = [0]*(n+1)
queue = [v]
already_visited[v] = 1
while queue:
v = queue[0]
del queue[0]
print(v, end=' ')
for i in range(1, n+1):
if adj_matrix[v][i] == 1 and already_visited[i] == 0:
queue.append(i)
already_visited[i] = 1
n, m, v = map(int, input().split())
adj_matrix = [[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
a, b = map(int, sys.stdin.readline().split())
adj_matrix[a][b] = 1
adj_matrix[b][a] = 1
already_visited = [0]*(n+1)
dfs(v)
print()
bfs(v)
Code 2
import sys
def dfs(v):
visited = {}
stack = [v]
while stack:
s = stack.pop()
if s not in visited:
visited.setdefault(s)
stack += reversed(adj_dict[s])
return visited
def bfs(v):
visited = {}
queue = [v]
while queue:
s = queue[0]
del queue[0]
if s not in visited:
visited.setdefault(s)
queue += adj_dict[s]
return visited
n, m, v = map(int, input().split())
adj_dict = {i:[] for i in range(1,n+1)}
for i in range(1,m+1):
a, b = map(int, sys.stdin.readline().split())
adj_dict[a].append(b)
adj_dict[b].append(a)
for k in adj_dict:
adj_dict[k].sort()
dfs_result = dfs(v)
bfs_result = bfs(v)
print(' '.join(list(map(str, dfs_result))))
print(' '.join(list(map(str, bfs_result))))
참고
Code1
: adjacency matrix를 이용하여 DFS, BFS를 구현하였다.
DFS는 재귀함수로, BFS는 queue로 구현하였다.
이미 방문한 노드를 list에 기록하였다.
Code2:
adjacency list를 이용하여 DFS, BFS를 구현하였다.
DFS는 stack으로, BFS는 queue로 구현하였다.
이미 방문한 노드를 dict로 기록하였다.
이미 방문한 노드를 list에 기록하고 확인하는 것 보다 dict을 이용하는 것이 더 빨랐다. 어떤 원소의 존재 유무를 확인하는 과정이 list보다 dict에서 효율적으로 가능하기 때문이다.
또한, Code 2가 Code 1보다 더 빠르다.
Author And Source
이 문제에 관하여(백준 - 그래프(# 1260)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@starteon/백준-그래프-1260저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)