[Algorithm] 백준 1260 - DFS와 BFS in Python(파이썬)

💡 백준 1260:

DFS & BFS 탐색

🌱 코드 in Python

알고리즘: DFS & BFS

import sys

input = sys.stdin.readline
n, m, v = map(int, input().split())
g = [[] for i in range(n + 1)]
visit = [0] * (n + 1) # 방문 확인 배열
q = []

for i in range(m):
	g1, g2 = map(int, input().split())
	g[g1].append(g2)
	g[g2].append(g1)

def dfs(s):
	q.append(s)
	while q:
		tmp = q.pop() 
		visit[tmp] = 1
		print(tmp, end=' ')
		g[tmp].sort() # 정점 번호가 작은 것을 먼저 탐색하기 위해 sort
		for i in g[tmp]:
			if visit[i] != 1:
				dfs(i) # 재귀 문으로 깊이 우선 탐색

def bfs(s):
	q.append(s)
	while q:
		tmp = q.pop(0)
		visit[tmp] = 1
		print(tmp, end=' ')
		for i in g[tmp]:
			if visit[i] != 1:
				visit[i] = 1
				q.append(i)

dfs(v)
print()
visit = [0] * (n + 1)
bfs(v)

이번 문제는 DFS와 BFS를 활용하는 기본 문제였다
정점 번호가 작은 것을 먼저 방문한다가 약간의 함정이라면 함정?!
나는 sort함수를 통해 해결했다

DFS같은 경우 이번에는 재귀문으로 풀어보았다
BFS는 지난 번 문제인 바이러스와 같은 형식으로 해결하였다

🧠 기억하자

1. 빨리 익숙해졌음 좋겠다 !

백준 1260 바로가기