[백준] 1260. DFS와 BFS
문제
고려해야 하는 반례
<채점 중 87%에서 런타임에러 발생>
1000 1 1
99 1000
반례에서 알아야 하는 부분
- 어떠한 간선도 존재하지 않는 노드가 존재한다. -> 해당 조건을 추가해줘야 한다.
import sys
from collections import deque
# 입력으로 들어온 간선 정보 저장
def makeGraph(points):
graph = dict()
for p in points:
# 간선은 양방향이기 때문에 각각의 노드에 연결된 노드에 대한 정보를 추가해주어야 한다.
# 모든 노드가 간선을 가지는 것이 아니다.
if not p[0] in graph.keys():
graph[p[0]] = []
if not p[1] in graph.keys():
graph[p[1]] = []
graph[p[0]].append(p[1])
graph[p[1]].append(p[0])
for g in graph:
graph[g].sort()
return graph
def dfs(graph, visited, v):
visited[v] = True
print(v, end=' ')
if v in graph: # 반례를 통해 알아낸 조건 추가
for i in graph[v]:
if not visited[i]:
dfs(graph, visited, i)
def bfs(graph, visited, v):
queue = deque([v])
visited[v] = True
while queue:
v = queue.popleft()
print(v, end=' ')
if v in graph: # 반례를 통해 알아낸 조건 추가
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
def start():
n, m, v = map(int, sys.stdin.readline().split())
points = [list(map(int, sys.stdin.readline().split())) for i in range(m)]
visited_dfs = [0] * (n+1)
visited_bfs = [0] * (n+1)
graph = makeGraph(points)
dfs(graph, visited_dfs, v)
print()
bfs(graph, visited_bfs, v)
start()
매번 까먹는 부분
bfs 구현 시 queue가 필요한데, 파이썬에서는 deque와 Queue로 구현할 수 있다.
deque
-
double-ended queue, 데이터 양방향 추가, 제거 가능
-
deck 이라고 읽음
-
thread-safe와 appends와 pops의 메모리 효율성 보장
-
deque는 초기화해줄 때, 다음과 같이 deque([5])
from collections import deque
queue = deque([4]) # queue -> 4
queue.append(5) # queue -> 4 5
queue.append(6) # queue -> 4 5 6
queue.popleft() # 4, queue -> 5 6
queue.popleft() # 5, queue -> 6
queue.clear() # queue ->
Queue
from queue import Queue
queue = Queue()
queue.put(4) # queue -> 4
queue.put(5) # queue -> 4 5
queue.put(6) # queue -> 4 5 6
queue.get() # 4, queue -> 5 6
queue.get() # 5, queue -> 6
queue.get() # 6, queue ->
Author And Source
이 문제에 관하여([백준] 1260. DFS와 BFS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@nayoon-kim/백준-1260-DFS와-BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)