[Python] 백준 1260번: DFS와 BFS

문제

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

1260번: DFS와 BFS

---

풀이

 

Dfs는 재귀, Bfs는 큐를 사용한다.(시간복잡도가 낮은 덱을 사용)

2차원 배열로 노드 연결여부를 구성. 최초 모든 연결을 False로 초기화

입력값에 따라 (시작노드,끝노드), (끝노드,시작노드)를 True로 만들어줌.(연결되었다)

visited1,visited2는 dfs,bfs의 방문기록 작성

깊이우선탐색, 너비우선탐색에서 조건문의 기준은

“방문하지 않았고, 연결이 되어있다면” 이다.

 

dfs는 재귀를 사용한다.

탐색을 시작할 정점의 번호 V부터 시작한다.

방문하지 않았고, 연결이 되어있다면 계속해서 재귀를 활용하여 깊이우선탐색을한다.

 

bfs는 큐(덱)을 사용한다

큐가 비어있지 않은동안 반복한다.

방문하지 않았고, 연결이 되어있다면 큐에 노드를 추가하고 방문처리해준다.

코드

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

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

#노드 연결여부
graph=[[False]* (n+1) for _ in range(n+1)]

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

visited1=[False]* (n+1) #dfs방문기록
visited2=[False]* (n+1) #bfs방문기록


def dfs(v): #재귀
    visited1[v]=True
    print(v,end=' ')
    for i in range(1,n+1):
        if not visited1[i] and graph[v][i]: # 만약 i값을 방문하지 않았고 V와 연결이 되어 있다면
            dfs(i)
def bfs(v): #큐
    q=deque([v]) #pop메서드의 시간복잡도가 O(1)로 작은 덱 내장 메서드 사용. 리스트사용시 poplast는 O(1)이지만, pop intermediate O(k)
    visited2[v] =True
    while q:
        v=q.popleft() #큐의 첫번째 값 꺼내기
        print(v,end=' ')
        for i in range(1,n+1):
            if not visited2[i] and graph[v][i]: ## 만약 i값을 방문하지 않았고 V와 연결이 되어 있다면
                q.append(i) #i 값(노드) 추가
                visited2[i] = True #i 값 방문 처리




dfs(v)
print()
bfs(v)