[Python3] 백준 1260번 DFS와 BFS

사용 언어 - Python3

문제 - DFS와 BFS

1260번: DFS와 BFS

 

정답

BFS, DFS 만들기 (정답 맞춘 여부 X)

0. input, 변수 선언

graph = 정점의 개수+1 만큼의 (n+1,n+1) 0벡터 배열을 만들어준다.

visit했는지 여부를 (n+1) 크기의 0벡터로 만든다. BFS, DFS 두개의 리스트로 만든다.

graph[a][b] = graph[b][a] = 1 입력되는 간선은 양방향이기 때문에 반대방향도 똑같이 1이다.

 

1. BFS(v)

from collections import deque

v 값(시작 번호)을 deque에 apped후 한개씩 삭제하면서 for문을 돌린다.

visit_list[i]가 0이고(=아직 방문하지 않음), graph[v][i]가 1(=간선이 연결되어 있는 번호) 인 경우 q에 i를 append하고, visit했다고 표시한다.

 

2. DFS(v)

재귀함수로 푼다.

방문했다고 표시후, for문을 돌린다. 조건 만족시 dfs(i)를 재귀적으로 돌린다.

from collections import deque
import sys
input = sys.stdin.readline

def bfs(v):
    q = deque()
    q.append(v)
    visit_list[v] = 1
    while q:
        v = q.popleft()
        print(v, end = " ")
        for i in range(1,n+1):
            if visit_list[i] == 0 and graph[v][i] == 1:
                q.append(i)
                visit_list[i] = 1
        
def dfs(v):
    visit_list2[v] = 1
    print(v, end = " ")
    for i in range(1,n+1):
        if visit_list2[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)]
visit_list = [0]*(n+1)
visit_list2 = [0]*(n+1)

for _ in range(m):
    a,b = map(int,input().split())
    graph[a][b] = graph[b][a] = 1

dfs(v)
print()
bfs(v)

 

 

 

---

레퍼런스

• 정답 참고

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

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부