1260.md

백준 1260번 DFS와 BFS

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

---

코드 설명

• dfs는 깊이 우선 탐색으로 (1 3),(1 4),(3 2) 이럴 경우 1에서 출발하면 3을 확인한 뒤 3과 연결된 2를 확인하는 식으로 한쪽을 깊숙히 다 확인한 뒤 나머지를 확인하는 방법이다.
• bfs는 너비 우선 탐색으로 (1 3),(1 4),(3 2) 이럴 경우 1에서 출발하면 3을 확인한 뒤 다시 1로 돌아와 4를 확인하는 식으로 node와 연결된 노드들을 모두 확인한 뒤 다음으로 넘어가 나머지들을 확인하는 방법이다.

소스코드

• 메모리 : 38216 KB
• 시간 : 628 ms

import sys

def dfs(node):
	visit_dfs[node] = 1
	print(node, end=" ")
	for nd in range(1,n+1):
		if visit_dfs[nd] == 0 and matrix[node][nd] == 1:
			dfs(nd)
	

def bfs(node):
	q = []
	visit_bfs[node] = 1
	q.append(node)
	
	while q:
		node = q.pop(0)
		print(node, end=" ")

		for nd in range(1, n+1):
			if visit_bfs[nd] == 0 and matrix[node][nd] == 1:
				q.append(nd)
				visit_bfs[nd] = 1
	
	
	

n, m, start = tuple(map(int,input().split()))
matrix = [[0]*(n+1) for _ in range(n+1)]
for i in range(m):
	x, y = tuple(map(int,input().split()))
	matrix[x][y] = matrix[y][x] = 1
visit_dfs = [0]*(n+1)
visit_bfs = [0]*(n+1)

dfs(start)
print()
bfs(start)