[BOJ] 1260번 DFS와 BFS (Python)

[BOJ] 1260번 DFS와 BFS (Python)

1260번: DFS와 BFS

• 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력
• 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문
• 더 이상 방문할 수 있는 점이 없는 경우 종료
• 정점 번호는 1번부터 N번까지.

from collections import deque

# 정점 개수, 간선 개수, 탐색 시작 정점
n, m, v = map(int,input().split())
# m개의 두 정점 번호
graph = [[] for _ in range(n + 1)] # 빈 배열 선언
# 연결 정보
for i in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)
  graph[a].sort()
  graph[b].sort()
  
# 깊이 우선, 재귀적으로 구현
def dfs(graph, visited, v):
  visited[v] = True # 현재 노드 방문 처리
  print(v, end = ' ') # 현재 노드 출력
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, visited, i) # 재귀

# 너비 우선, queue
def bfs(graph, visited, v):
  queue = deque([v]) # 큐 선언, 시작 노드 큐에 삽입
  visited[v] = True # 시작 노드 방문 처리
  while queue: # 큐가 빌때까지
    node = queue.popleft()
    print(node, end = ' ')
    # 연결된 노드 중 방문하지 않은 노드를 큐에 삽입
    for i in graph[node]: 
      if not visited[i]:
        queue.append(i) 
        visited[i] = True
        
visited = [False] * (n + 1)
dfs(graph, visited, v)
print()
visited = [False] * (n + 1)
bfs(graph, visited, v)

from collections import deque

n, m, v = map(int, input().split())

graph = [[] for _ in range(n+1)]

for i in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

for i in graph:
  i.sort()
  
def dfs(graph, visited, v):
  visited[v] = True
  result1.append(v)
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, visited, i)
  return result1
  
def bfs(graph, visited, v):
  queue = deque([v])
  visited[v] = True
  while queue:
    now = queue.popleft()
    result2.append(now)
    for i in graph[now]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True
  return result2

result1 = []
visited = [False] * (n+1)
print(*dfs(graph, visited, v))
result2 = []
visited = [False] * (n+1)
print(*bfs(graph, visited, v))

 

---

2023.07.18 복습

from collections import deque
# dfs, 깊이우선탐색, 스택(리스트), 재귀로 구현
def dfs(graph, visited, v):
  visited[v] = True # 방문 처리하고
  print(v, end = ' ')
  for i in graph[v]: # 현재 노드에 연결된 노드를 탐색
    if not visited[i]: # 방문하지 않은 노드라면
      visited[i] = True # 방문 처리하고
      dfs(graph, visited, i) # dfs 수행

# bfs, 너비우선탐색, 큐(deque), while로 구현
def bfs(graph, visited, v):
  visited[v] = True # 방문처리하고
  queue = deque([v]) # 큐에 넣어줌
  while queue: # 큐에 노드가 있는 동안
    now = queue.popleft() # 큐에서 노드를 꺼내줌
    print(now, end = ' ')
    for i in graph[now]: # 현재노드에 연결된 노드를 탐색
      if not visited[i]: # 연결된 노드가 방문하지 않은 노드라면
        visited[i] = True # 방문처리
        queue.append(i) # 큐에 넣어줌

  
n, m, v = map(int, input().split())
graph = [[] for _ in range(n+1)] # 노드 개수 만큼 2차원 그래프 생성 
for _ in range(m): # 간선 개수만큼 입력받기
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

# 그래프 노드를 오름차순으로 정렬
for i in graph:
  i.sort()

visited = [False] * (n+1)
dfs(graph, visited[:], v)
print()
bfs(graph, visited[:], v)