너비 우선 탐색(BFS)

너비 우선 탐색(BFS)

from collections import deque

#BFS 메서드 정의
def bfs(graph, start, visited):
	# 큐(Queue) 구현을 위해 deque 라이브러리 사용
	queue = deque([start])
	# 현재 노드를 방문 처리
	visited[start] = True
	# 큐가 빌 때까지 반복
	while queue:
		# 큐에서 하나의 원소를 뽑아 출력하기
		v = queue.popleft()
		print(v, end=' ')
		# 아직 방문하지 않은 인접한 원소들을 큐에 삽입
		for i in graph[v]:
			if not visited[i]:
				queue.append(i)
				visited[i] = True

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
	[],
	[2,3,8],
	[1,7],
	[1,4,5],
	[3,5],
	[3,4],
	[7],
	[2,6,8], 
	[1,7]
]

# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited=[False]*9

# 정의된 DFS 함수 호출
bfs(graph,1,visited)

>>> 1 2 3 8 7 4 5 6  

# 미로 탈출
# BFS 소스코드 구현
def bfs(x,y):
	# 큐(Queue) 구현을 위해 deque 라이브러리 사용
	queue = deque()
	queue.append((x,y))
	# 큐가 빌 때까지 반복하기
	while queue:
		x,y= queue.popleft()
		# 현재 위치에서 4가지 방향으로의 위치 확인
		for i in range(4):
			nx=x+dx[i]
			ny=y+dy[i]
			# 미로 찾기 공간을 벗어난 경우 무시
			if nx<0 or nx>=n or ny<0 or ny>=m:
				continue
			# 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
			if graph[nx][ny] ==1:
				graph[nx][ny]=graph[x][y]+1
				queue.append((nx,ny))
	# 가장 오른쪽 아래까지의 최단 거리 반환
	return graph[n-1][m-1]

from collections import deque

# N, M을 공백을 기준으로 구분하여 입력 받기
n,m =map(int,input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph=[]
for i in range(n):
	graph.append(list(map(int,input())))

# 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
dx = [-1,1,0,0]
dy = [0,0,-1,1]

# BFS를 수행한 결과 출력
print(bfs(0,0))