[baekjoon] 백준 1260 번 : DFS와 BFS (by python 파이썬)

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

1260번: DFS와 BFS

 

 

정답  code

#DFS 와 BFS
from collections import deque
import sys
input = sys.stdin.readline
def dfs(v):
    print(v, end = ' ')
    visit[v] = True
    for i in graph[v]:
        if visit[i] == False:
            dfs(i)

def bfs(n):
    visit[n] = True
    queue = deque([n])
    while queue:
        v = queue.popleft()
        print(v, end= ' ')
        for i in graph[v]:
            if not visit[i]:
                queue.append(i)
                visit[i] = True


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

for i in range(m):
    v1,v2 = map(int,input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

for i in range(1, n+1):
    graph[i].sort()


visit = [False] * (n+1)
dfs(v)
print()
visit = [False] * (n+1)
bfs(v)

 

 

이번 문제는 dfs와 bfs의 기본형 문제다.

깊이 우선 탐색과 너비 우선 탐색의 기본형을 공부 해볼 수 있었다.

 

solution

1. 2차원리스트를 만들어 0부터 정점의 갯수만큼 할당

2. 입력받은 간선의 좌표를 해당 정점의 위치에 저장

3. 정점 별로 정렬

4. dfs bfs함수 실행

 

dfs (스택-> 재귀사용)

1. 입력 정점 출력

2. 출력 정점 방문표시 

3. 해당 정점의 이어져있는 정점 조사후 방문안했을시 dfs재실행

 

bfs (큐사용)

1. 입력정점 방문처리

2. 큐생성

3. 큐 존재시 fifo에 의해 삭제후 출력

3. 해당 정점에 이어진 정점에대해 방문 하지 않은 정점이 있을시 큐에 추가후 방문처리