백준 1260 DFS와BFS

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

1260번: DFS와 BFS

문제 자체는 아무런트릭이 없지만 그래프 탐색 알고리즘을 먼져 공부해야 풀 수 있는 문제

 

깊이 우선 탐색(BFS -Depth-First Search)

은 말 그대로 깊이를 우선하는 탐색이다.

재귀함수를 이용하여 구현하며, 가장 깊은곳까지 탐색한 후 더이상의 노드가 없을 때,

그제서야 그 전 단계의 다른 노드를 탐색한다.

구글링을 통해 그림을 찾아왔다.

## 코드##

def dfs(graph,v,visited):
    visited[v]=True
    print(v,end=' ')

    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i , visited)

 

너비 우선 탐색(BFS, Breadth-First Search)

DFS가 끝을 보고서야 돌아왔다면, 얘는 순차적이다.
시작 노드에서 방문할 수 있는 노드를(깊이1) 모두 방문한 뒤, 그 후에  깊이 1인 모든 노드에서 방문가능한 모든 노드를 방문한다.

##코드##

from collections import deque
#deque를 안쓰고 pop(0)을 활용해도 됨
def bfs(graph, start,visited):

    q=deque([start])
    visited[start]=True

    while q:
        v=q.popleft()
        print(v,end='->')
        for i in graph[v]:
            if not visited[i]:
                q.append(i)
                visited[i]=True

 

이 개념들을 바탕으로, 입력받아서 그래프를 구현 후 풀어나가자

 

##전체문제풀이##

def dfs(graph,v,visit1):
    visit1[v]=True
    print(v,end=' ')

    for i in graph[v]:
        if not visit1[i]:
            dfs(graph,i,visit1)

def bfs(graph, v, visit2):
    q=[]
    visit2[v]=True
    q.append(v)

    while q:
        tmp=q.pop(0)
        print(tmp, end=' ')
        for i in graph[tmp]:
            if not visit2[i]:
                q.append(i)
                visit2[i]=True

    




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

graph=[[]for _ in range(n+1)]

for _ in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
for g in graph:
    g.sort()
visit1=[False for _ in range(n+1)]
visit2=visit1.copy()

dfs(graph,v,visit1)
print()
bfs(graph,v,visit2)