[알고리즘] 백준 1260 파이썬 - DFS와 BFS

 

1260번: DFS와 BFS

 

문제

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

 

문제풀이

from collections import deque
import sys
input = sys.stdin.readline
n,m,v = map(int,input().split())
#노드(즉 정점간의 연결 여부를 확인하는 용도)
graph=[[0]*(n+1) for _ in range(n+1)]   
#방문 확인용
visited = [0]*(n+1)

#graph에 정점 간에 연결이 되어있다면 1로 표시해준다.
for i in range(m):
    a,b=map(int,input().split())
    graph[a][b]=graph[b][a]=1

#01
def dfs(v):
    visited[v]=1
    print(v,end=' ')
    for i in range(1,n+1):
        if(visited[i]==0 and graph[v][i]==1):
            dfs(i)
#02
def bfs(v):
    queue=[v]
    visited[v]=0
    while queue:
        v=queue.pop(0)
        print(v, end=' ')
        for i in range(1,n+1):
            if visited[i]==1 and graph[v][i]==1:
                queue.append(i)
                visited[i]=0 
dfs(v)
print()
bfs(v)

 

- 우선 풀이에 앞서 DFS와 BFS의 설명은 아래 링크를 참조하면 된다.

[알고리즘] 백준 2606 파이썬 - 바이러스(DFS 풀이)

- #01 : dfs 즉 깊이우선탐색이다. 보통 재귀함수를 사용하여 구현한다. 

           시작점 v부터 방문 후 vistied에 방문하였다고 1로 바꿔준다.

           이후 for문을 통해 visited 값이 0이고 graph에 v와 연결된 i 값을 찾는다.

           찾았다면 다시 dfs(i)를 해준다. 

- #02 : bfs 즉 넓이우선탐색이다. 보통 queue, deque 등을 통해 구현한다.

           queue에 시작값 v를 넣고 이번엔 visited 값이 #01 과정으로 인해 모두 1이므로,

           0으로 바꿔준다. 이후 while문을 통해 바로 queue의 값을 pop해준다. 

           아까 dfs 함수에서 봤던 조건이랑 똑같다. 하지만 여기선 반복문을 통해 

           구현하므로, 출력되는 순서가 달라진다. 즉 1 이후 queue에 for문을 통해 2,3,4가

           한번에 추가된다. 이후 queue는 pop을 통해 2,3,4 형태로 하나씩 출력한다.

 

- 처음 알고리즘을 접하는 사람에게는 상당히 어려운 개념이다.

  하지만 상당히 자주 나오는 알고리즘 중 하나이다. 그렇기에

  코딩테스트를 위해서는 기본적으로 숙지하고 있어야 된다.

  아마 한 번에 이해하기 어렵기에 스스로 손으로 결과값을 써보며,

  하나씩 따라가면서 학습하는 것이 더욱 오래 기억에 남을 것이다.