[BOJ] 1260 python

bfs와 dfs 문제

https://velog.io/@hamfan524/%EB%B0%B1%EC%A4%80-1260%EB%B2%88-Python-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준] 1260번-(Python 파이썬) - Bfs, Dfs

 

논문에서 그래프 탐색할 때에도 항상 bfs 와 dfs 로 나오는데, 

요새 각성되어있는 까닭인가, 아니면 여서 설명이 가장 깔끔하기 때문인가 이 설명보고 두가지의 탐색 방법에 대해서 이해가 되었다.

 

가장 큰 차이점이,

dfs 의 경우 재귀적으로 접근을 하고,

bfs 의 경우 데큐를 사용하여서 해를 탐색한다. 

 

이 접근법이 dfs와 bfs를 이해하는 데 가장 이해하기 좋은 설명이 아닐까.

# bfs와 dfs 구현
from collections import deque
import sys
input=sys.stdin.readline

def bfs(v): # 데큐에 저장 
    q=deque()
    q.append(v)
    visited[v] = 1
    while q:
        v=q.popleft()
        print(v, end=' ')
        
        for i in range(1,n+1):
            if visited[i]==0 and graph[v][i]==1:
                q.append(i)
                visited[i]=1
                
def dfs(v): # 재귀적으로 접근 
    visited2[v] = 1
    print(v, end=' ')
    
    for i in range(1, n+1):
        if visited2[i] == 0 and graph[v][i] == 1:
            dfs(i) # 재귀로 표현이 되는 거

            
n,m,v = map(int, input().split())

graph=[[0]*(n+1) for _ in range(n+1)] # 그래프 메모리 할당
visited=[0]*(n+1) # 정점1
visited2=[0]*(n+1) # 정점2

for _ in range(m): # 5 : 엣지의 관계성
    a,b=map(int,input().split())
    graph[a][b]= graph[b][a] = 1 # 관계성이 있다면, 무방향그래프에서 1
    
dfs(v)
print()
bfs(v)

 

알다시피 이 두 탐색법은 코테에서 필수적인 탐색법이고, 논문에서 자주 언급되고 있는 그래프 탐색 기법들이다.

처음으로 구현해 본 것 같다. 다양한 문제로 이해를 쌓자. 굿