백준_2178_미로 탐색

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

2178번: 미로 탐색

해결 방법

> BFS를 활용한다.

> 미로에 최단거리의 업데이트를 하지 말고 또 다른 하나의 2차원 배열을 만들어 그곳에서 최단거리를 관리한다.

> dx = [0,0,1,-1] dy = [1,-1,0,0]을 활용하여 상하좌우를 탐색한다.

 

코드

import collections

 

y, x = map(int,input().split())

 

maze = []

queue = collections.deque([])

visited = [[0]*x for i in range(y)] #최단거리 정보 배열

 

for i in range(y):

    maze.append(input())

 

queue.append((0,0))

visited[0][0] = 1

while queue:

 

    dx = [0,0,1,-1]

    dy = [1,-1,0,0]

 

    t = queue.popleft()

 

    _x = t[0]

    _y = t[1]

 

    if _x == x - 1 and _y == y - 1:

        print(visited[_y][_x])

        break

 

    for i in range(4):

        nx = _x + dx[i]

        ny = _y + dy[i]

        if nx < x and nx >= 0 and ny < y and ny >= 0: #index check

            if visited[ny][nx] == 0 and maze[ny][nx] == '1':

                visited[ny][nx] = visited[_y][_x] + 1

                queue.append((nx,ny))