[Python] 백준 1260번 : DFS와 BFS (S2) - DFS&BFS단계별1

#문제

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

#풀이 & 학습한 내용

"DFS와 BFS를 다루는 문제"입니다. DFS는 스택을 이용하는 알고리즘이며, 재귀 함수를 이용해서 간결하게 구현할 수 있습니다. 파이썬에서 스택을 이용할 때는 별도의 라이브러리를 사용할 필요 없이 기본 리스트에서 append()와 pop() 메서드를 이용하면 됩니다. 또한, BFS는 큐를 이용하는 알고리즘입니다. 파이썬에서 큐를 구현할 때는 collections모듈의 deque자료구조를 이용하는 것이 queue자료구조보다 더 효율적이고 간단합니다.

 

그리고 그래프를 표현하는 2가지 방법인 인접 행렬과 인접 리스트는 파이썬에서 모두 2차원 리스트를 이용하여 표현합니다. 이때, 초기화하는 방법으로 아래 코드의 27번째 줄을 기억해둘 필요가 있습니다.

 

 

 

#소스코드(25, 27번째 줄 주목)

from collections import deque
 
def dfs(graph,V,visited):
  visited[V]=True #방문처리
  print(V, end=' ')
  for i in graph[V]:
    if not visited[i]: #인접한 노드중 방문안된 노드
      dfs(graph,i,visited) #재귀로 시작노드 바꿔서 호출
 
def bfs(graph,start,visited):
  queue = deque([start]) #큐에 시작노드 추가
  visited[start]=True #방문처리
  while queue:
    v = queue.popleft() #큐에서 하나 뽑기
    print(v,end=' ')
    for i in graph[v]:
      if not visited[i]:
        queue.append(i) #방문 안된 인접한 노드 모두 큐에 추가
        visited[i]=True #방문처리(다른경우에서 또 큐에 추가 안하기 위해)
 
 
N,M,V = map(int,input().split())
 
#방문여부 확인하는 리스트 초기화
visited=[False]*(N+1)
#인접리스트 초기화
graph = [[] for _ in range(N+1)]
 
#인접리스트로 그래프 저장
#번호낮은순으로 처리하도록 정렬
for i in range(M):
  v1,v2 = map(int,input().split())
  graph[v1].append(v2)
  graph[v1].sort()
  graph[v2].append(v1)
  graph[v2].sort()
 
dfs(graph,V,visited)
print()
 
#모든 노드 방문안됐음으로 초기화
visited=[False]*(N+1)
bfs(graph,V,visited)
print()

 

github.com/HoYoungChun/Algorithm_PS/blob/master/DFS%26BFS/BOJ_1260.py

HoYoungChun/Algorithm_PS

 

※ 두 번째 풀었을 때

dfs와 bfs의 원리를 명확히 이해하고 다른 자료를 참고하지 않고, 코드를 구현했습니다. 더 많이 코드를 짜서 익숙해질 필요가 있습니다. dfs와 bfs를 설명할 수 있는 상태가 되어야 다른 활용이 가능할 것입니다.

 

 

두 번째 풀었을때의 코드(2021/03/08)

from collections import deque #bfs에서 큐 쓰기위해

'''dfs'''
def dfs(now_v):
  visited[now_v]=True #★방문처리 여기서
  print(now_v, end=' ')
  for new_v in maps[now_v]: #인접한 vertex가
    if not visited[new_v]: #방문안했으면
      dfs(new_v) #재귀호출

'''bfs'''
def bfs(q):
  while q: #큐 비면 경로있는애들은 다 방문한거다
    now_v=q.popleft() #큐에서 하나 뽑기
    print(now_v, end=' ')
    for new_v in maps[now_v]: #인접한 vertex가
      if not visited[new_v]: #방문안했으면
        visited[new_v]=True #★방문처리 여기서
        q.append(new_v) #재귀가 아닌 한번에 큐에 넣어주기


N,M,V=map(int,input().split())
vertex_num=N
edge_num=M
start_vertex=V

#인접리스트로 표현된 그래프 저장할 리스트
maps=[[]for _ in range(vertex_num+1)]
#방문여부 저장할 리스트
visited=[False]*(vertex_num+1)

#인접리스트로 그래프 저장완료
for _ in range(M):
  v1,v2=map(int,input().split())
  maps[v1].append(v2)
  maps[v2].append(v1)
  maps[v1].sort()
  maps[v2].sort() #번호 작은 vertex부터 방문하기 위해 sort

'''dfs'''
dfs(start_vertex) #시작 vertex 인자로 전달


visited=[False]*(vertex_num+1) #방문여부 초기화
print() #개행


'''bfs'''
visited[start_vertex]=True # 시작 vertex 방문처리
q=deque([start_vertex]) #큐에 시작 vertex넣어주기
bfs(q)

github.com/HoYoungChun/Algorithm_PS/blob/master/DFS%26BFS/BOJ_1260_2.py

HoYoungChun/Algorithm_PS