[Python] BOJ(백준) 1260번 - DFS와 BFS

1. 링크

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

2. 난이도(solved.ac 참고)

실버2

3. 풀이

	# https://www.acmicpc.net/problem/1260
	from collections import deque
	import sys
	f = sys.stdin.readline
	# DFS
	def dfs(graph, v, visited):
	visited[v] = True
	print(v, end=' ')
	for i in sorted(graph[v]):
	if not visited[i]:
	dfs(graph, i, visited)
	# BFS
	def bfs(graph, v, visited):
	queue = deque([v])
	visited[v] = True
	while queue:
	q = queue.popleft()
	print(q, end=' ')
	for i in sorted(graph[q]):
	if not visited[i]:
	queue.append(i)
	visited[i] = True
	# 인접 리스트
	n, m, v = map(int, f().split()) # n: 정점의 개수, m: 간선의 개수, v: 시작점
	visited_DFS = [False] * (n+1)
	visited_BFS = [False] * (n+1)
	adjList = [[] for _ in range(max(n, m)+1)]
	for i in range(m):
	start, dest = map(int, f().split())
	adjList[start].append(dest)
	adjList[dest].append(start)
	dfs(adjList, v, visited_DFS)
	print()
	bfs(adjList, v, visited_BFS)

view raw DFS와BFS.py hosted with ❤ by GitHub

걍 뭐.. 설명할 것도 없다. 이거 못풀면 다른 모든 그래프 탐색 문제도 못 푼다..

일반적인 DFS와 BFS 구현에서 아주 살짝 달랐던 점은, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다는 점이다. 이 부분은, v 지점을 방문 표시한 뒤에 인접 리스트의 인덱스 v를 기준으로 연결된 여러 정점 중 가장 작은 것부터 방문해야 된다는 뜻이다. 따라서, graph에 대한 for문을 돌 때 sorted() 처리를 해주면 된다.

 

아 그리고, 인접 리스트의 총 길이는 n과 m 중 큰 값 + 1만큼 되어야 한다는 점도 고려해야 한다.

예를 들어 정점은 1000개지만 간선은 1개일 때나, 정점은 5개지만 간선이 6개일 때를 생각해보면 n이나 m 중 어느 한 값으로 고정시킬수는 없다는 것을 알게 될 것이다.