[DFS/BFS/완전탐색] 1260번 - DFS와 BFS

[백준] 1260번 - DFS와 BFS

풀이 시간: 35분 이내

 

1) 문제 해결 아이디어

그래프를 DFS, BFS로 탐색한 결과를 출력하는 문제였다.

DFS는 재귀함수로 BFS는 큐(deque)로 구현하였다.

 

인접 노드 방문 조건: 정점 번호가 작은 순서

여기서는 방문할 수 있는 인접 노드가 여러 개인 경우에 정점 번호가 작은 것을 먼저 방문하는 조건이 있기 때문에 각 정점별 인접 노드 번호를 오름차순으로 정렬해주어야한다.

 

개인적으로 반복문을 이용하여 구현하는 BFS보다 재귀함수를 이용해야하는 DFS가 조금 더 익숙치 않아 어려운 것 같다.

현재 노드를 방문처리하고 인접 노드를 검사하는 것까지는 동일하지만

DFS에서는 인접 노드가 방문되지 않은 노드라면 해당 노드를 재귀호출하고

BFS에서는 인접 노드가 방문되지 않은 노드라면 계속 방문처리를 수행한다.

 

2) 소스코드

from collections import deque

# 정점 개수, 간선 개수, 탐색 시작 번호
n, m, v = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [False] * (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()    

# DFS
def dfs(v):
  # 현재 노드 삽입, 방문처리
  visited[v] = True
  print(v, end=" ")

  # 인접 노드 탐색
  for i in graph[v]:
    # 방문하지 않은 노드이면
    if not visited[i]:
      dfs(i)
  
# BFS
def bfs(v):
  queue = deque()
  # 시작점 삽입, 방문처리
  queue.append(v)
  visited[v] = True

  while queue:
    # 꺼내기
    v = queue.popleft()
    print(v, end=" ")
    
    # 꺼낸 노드의 인접 노드 탐색
    for i in graph[v]:
      # 가보지 않은 곳이면
      if not visited[i]:
        # 삽입, 방문처리
        queue.append(i)
        visited[i] = True

dfs(v)
print()
visited = [False] * (n + 1)  # 방문 여부 초기화
bfs(v)