[CodingTest] BOJ1260 DFS와BFS ( DFS,BFS ) With 파이썬

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

1260번: DFS와 BFS

 

 

◎ 문제풀이

 

DFS, BFS 문제이다. 

 

DFS는 STACK, BFS는 QUEUE를 사용하면 된다. 재귀호출은 함수가 STACK 영역에 쌓이므로 재귀호출로 구현한다. 

 

주의점 

1) BFS에서 노드 방문이력은 큐에 들어가기 직전에 변경해야한다.

2) 양방향 관계임을 주의하자.

3) 인접노드 탐색시 오름차순 순으로 탐색해야 하므로 정렬이 필요하다. 

 

◎ 코드

from collections import deque

n,m,start = map(int,input().split())
edges = [[] for _ in range(n+1)]

# 간선 초기화
for _ in range(m) :
  a,b = map(int,input().split())
  edges[a].append(b)
  edges[b].append(a)

# 인접노드 오름차순 정렬
for i in range(n+1) :
  edges[i].sort()

# DFS
def dfs(edges,v,visited) :
  print(v,end=" ")
  visited[v] = True
  for next in edges[v] :
    if not visited[next] : dfs(edges,next,visited)

#BFS
def bfs(edges,v,visited) :
  q = deque([v])
  visited[v] = True
  while q  :
    node = q.popleft()
    print(node,end=" ")
    for next in edges[node] :
      if not visited[next] :  
        visited[next] = True 
        q.append(next)

# 수행
visited = [False] * (n+1) #방문이력테이블
dfs(edges,start,visited) 
print()
visited = [False] * (n+1) #방문이력테이블 원복
bfs(edges,start,visited)