문제
https://www.acmicpc.net/problem/1260
풀이
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)
'Koala - 11기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준/python3] 9657번 : 돌 게임 3 (0) | 2023.08.19 |
---|---|
[백준/Python] 9372번 상근이의 여행 (0) | 2023.08.19 |
[C++] 백준 2606번: 바이러스 (0) | 2023.08.16 |
[백준/python] 4949번 균형잡힌세상 (0) | 2023.08.14 |
[백준/C++] 2346번 : 풍선 터뜨리기 (0) | 2023.08.14 |