1260 DFS와 BFS

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

#DFS

#BFS

1260번: DFS와 BFS

#dfs 와 bfs

 

they stand for depth first search and breadth first search.

그래프로 따졌을때 가지가 있다고 생각해보자 한 가지를 정해서 깊숙하게 다 탐색한 후 채워나가고 다 채워나가지면 다른 가지를 정한다 이게 dfs 모든 가지에서 같은 단계에 있는 애들을 하나씩 채우면서 내려간다 이게 bfs

 

#1260 코드

 

import sys

sys.setrecursionlimit(10**6)
#재귀 한계 늘리기

input=sys.stdin.readline
#스탠다드 인풋

n,m,v=map(int,input().split())
#정점 간선 첫 정점번호 입력

order=[[] for i in range(n+1)]
#순서를 넣을 리스트 작성

for i in range(m):

a,b=map(int,input().split())

order[a].append(b)

order[b].append(a)

[i.sort() for i in order]

#이해하기 좀 어려웠는데 다익스트라 때문에 헷갈렸던것 같다. 여기서 간선은 연결한 것이지 먼저 나오는 것이 아니며 ##문제에서 정점이 여러개이면 낮은 수부터이기 때문에 sort(reverse=True) 가 아닌 오름차순으로 정렬

 

dfs_answer=[]

bfs_answer=[]

#답을 담을 리스트

 

visited=[False]*(n+1)

#지나갔는지 확인하는 리스트

 

def dfs(v):

visited[v]=True

dfs_answer.append(v)

for i in order[v]:

if visited[i]==False:

dfs(i)

#dfs

 

dfs(v)

print(*dfs_answer)

 

def bfs(v):

que=[v]

while que:

now=que.pop(0)

visited[now]=True

bfs_answer.append(now)

for i in order[now]:

if visited[i]==False:

que.append(i)

visited[i]=True

 

visited=[False]*(n+1)

bfs(v)

print(*bfs_answer)

 

#일단 dfs와 bfs도 위 코드상으로는 그렇게 다르지 않다. 다만 스택을 사용하여 저장해서 차례대로 하냐 아니면 탐색하는 대로 넣어버리냐 에 차이였다. dfs와 bfs에 대한 이해는 충분한 것 같으나 이를 구현하는 능력이 아직 부족한 것같다.