[Python] BOJ(백준) 2178번 - 미로 탐색

1. 링크

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

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

실버1

3. 풀이

	import sys
	from collections import deque
	input = sys.stdin.readline
	n, m = tuple(map(int, input().split()))
	alist = [list(map(int, input().strip())) for _ in range(n)]
	visited = [[False for _ in range(m)] for _ in range(n)]
	dx = [-1, 1, 0, 0]
	dy = [0, 0, -1, 1]
	def bfs(x, y):
	q = deque([(x, y, 1)])
	visited[x][y] = True
	while q:
	x, y, distance = q.popleft()
	if x == n-1 and y == m-1:
	print(distance)
	break
	else:
	for i in range(4):
	nx = x + dx[i]
	ny = y + dy[i]
	if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and alist[nx][ny] == 1:
	visited[nx][ny] = True
	q.append((nx, ny, distance + 1))
	bfs(0, 0)

view raw BOJ2178.py hosted with ❤ by GitHub

이 문제를 왜 지금까지 안 풀었었는지 모르겠다. BFS(DFS도 쓸 수 있긴 함)의 너무 기본적인 문제라 쓰기도 좀 애매하긴 한데..

 

값을 받아오고 각 위치별로 방문 여부를 확인하는 visited 배열을 선언해준다. 그다음 0, 0 위치에서 BFS 함수를 시작하면서

1) nx와 ny가 미로를 벗어났는지 확인

2) (nx,ny) 좌표를 이미 방문했는지 여부를 확인

3) 1, 2 모두 충족했을 경우 해당 좌표가 벽인지 확인(0이면 벽, 1이어야 지나갈 수 있는 길임)

이 경우 방문처리를 하고 큐에 지금까지 이동한 값인 distance에 1을 더한 값을 넣는다. 시작점도 거리에 포함한다고 했으므로 초기에 들어가는 값은 1이다.

좌표가 (n-1, m-1)이 되었을 때 그 위치로 오기까지의 거리인 distance를 출력해준다.