[백준/Python] 2178번 미로 탐색

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

2178번: 미로 탐색

---

Solution

	from collections import deque
	def bfs():
	q = deque()
	q.append((0,0))
	distance = [[0] * m for _ in range(n)]
	distance[0][0] = 1
	cnt = 1
	while q:
	x, y = q.popleft()
	for dx, dy in (-1,0), (1,0), (0,-1), (0,1):
	nx, ny = x+dx, y+dy
	if nx < 0 or nx >= m or ny < 0 or ny >= n:
	continue
	if maze[ny][nx] == '1' and distance[ny][nx] == 0:
	distance[ny][nx] = distance[y][x] + 1
	q.append((nx, ny))
	return distance[n-1][m-1]
	n, m = map(int, input().split(' '))
	maze = [input() for _ in range(n)]
	print(bfs())

view raw 미로탐색.py hosted with ❤ by GitHub

 

 

미로를 탐색해나가면서 가중치를 구해야 하기 때문에 BFS를 써야 한다. BFS의 개념과 문제에서 미로의 배열이 붙어서 주어지므로 문자열로 처리하는 것과, 시작 위치와 도착 위치도 카운트 해주는 것에 주의하면 크게 어렵지않게 풀 수 있다.

 

시작은 (0, 0) 부터 시작하므로, 큐에 (0, 0)을 넣어준다. 그리고 distance 배열을 만들고 시작 위치도 카운트 해주므로 [0][0]위치의 값은 1로 초기화 해준다. 큐를 돌면서 지나갈 수 있고(maze 배열의 값이 '1') 아직 방문하지 않았으면(distance 배열의 값이 0) 전에 방문했던 위치의 거리에 1을 더해 현재 위치 거리를 초기화해준다. 그리고 도착 위치의 거리 값을 리턴하고 출력한다^_^