백준 1260 DFS와BFS

Table of Contents

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

1260번: DFS와 BFS첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사www.acmicpc.net

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

깊이 우선 탐색(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)

코드###

코드##
#