[백준 / Python] 2178번 미로 탐색 | 초코더

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

2178번: 미로 탐색

 

접근법

matrix 는 101111 101010 101011 111011 를 입력받은 리스트입니다.

visited 는 [0]으로 이루어진 mxn 크기 리스트입니다.

dx, dy는 상하좌우를 나타내는 리스트입니다.

queue에는 가장 첫 시작점인 [[0,0]]이 들어갑니다.

visited[0][0]은 방문한 곳이므로 1로 바꿔줍니다.

 

- while문을 살펴보겠습니다.

- x,y좌표에는 queue의 가장첫번째 원소대입.(현재는 0,0)

- for문은 상하좌우 4번 반복합니다.

- 가장 처음 i가 0이 들어가므로 nx=-1, ny=0 (즉, 상하좌우중 좌를 살펴봅니다.)

- if문은 nx와 ny가 범위를 벗어날 경우 for문으로 올라가서 다른 경우를 비교해줍니다.

- 만약 범위를 통과한다면,

- matrix[nx][ny] 가 1이고(=갈수있는 곳인지) and visited[nx][ny] 가 0이면(=방문하지 않은 곳인지)

- visited[nx][ny] = visited[x][y] + 1 (visited[x][y]는 현재 1입니다. visited는 단순히 방문한지 안한지를 알려주는

  용도가 아닌 총 거리의 합을 구해주어야 하므로 현재 vistied에다가 1을 더해준 수를 저장.)

 

- print(visited[n-1][m-1]) #n,m길이인데 0,0부터 시작하므로 [n-1][m-1]

 

나의 풀이

import sys

n,m=list(map(int,sys.stdin.readline().split()))
matrix=[list(map(int,[pos for pos in sys.stdin.readline().strip()])) for _ in range(n)]
visited = [[0]*m for _ in range(n)]

dx = [-1,0,1,0]
dy = [0,1,0,-1]
queue=[[0,0]]
visited[0][0] = 1

while queue:
    x,y=queue.pop(0)
    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 matrix[nx][ny] == 1 and visited[nx][ny] == 0:
            visited[nx][ny] = visited[x][y] + 1
            queue.append([nx, ny])
print(visited[n-1][m-1])