백준 1260 DFS와 BFS

 

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

DFS의 경우 일반적으로 잘 아는 재귀함수를 통한 노드 방문 알고리즘을 생각하면 되지만 개인적으로 큐를 이용하여 BFS를 풀이하는 방식이 특이하다고 생각했다. 해당 알고리즘에 대한 설명과  풀이는 다음 사이트에서 참고하였다

https://velog.io/@falling_star3/%EB%B0%B1%EC%A4%80Python-1260%EB%B2%88-DFS%EC%99%80BFS

[백준][Python] 1260번 DFS와 BFS(DFS/BFS 기본 구현 자세히)

 

문제풀이

#N:정점의 수, M: 간선의 수, V: 탐색 시작 정점
N,M,V = map(int, input().split())
graph = [[0]*(N+1) for _ in range(N+1)]

for i in range(M):
  x, y = map(int,input().split())
  graph[x][y] = 1
  graph[y][x] = 1

#방문 여부의 알고리즘 
#visited의 index가 방문한 노드 value는 방문 여부
visited1 = [0]*(N+1)
visited2 = visited1.copy()

#DFS 함수-V는 방문할 노드를 의미
def dfs(V):
  #입력 받은 노드를 방문한다
  visited1[V] = 1
  print(V, end = ' ')
  for i in range(1, N+1):#1번부터 N번 노드까지
  #만약 탐색하는 정점을 방문한적이 없지만 그래프에는 생성이 되었다면
    if graph[V][i] == 1 and visited1[i] == 0:
      #해당 노드를 중심으로 다시 탐색해라
      dfs(i)

def bfs(V):
  queue = [V]
  visited2[V] = 1
  while queue: #큐가 비어있지 않은 동안
    V = queue.pop(0) # 방문한 노드는 제거
    print(V, end = ' ')
    for i in range(1, N+1):
      if(visited2[i] == 0 and graph[V][i] == 1):
        queue.append(i)
        visited2[i] = 1
dfs(V)
print()
bfs(V)