[BOJ / 백준] 2178번 미로 탐색 파이썬(Python) 문제 풀이

문제

 

문제 링크 : https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

 

 

CODE

from collections import deque
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
miro = []
for i in range(n):
    miro.append(list(input().rstrip()))

visited = [[0] * m for _ in range(n)]
dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs(x, y):
    q = deque([[x, y]])
    visited[y][x] = 1

    while q:
        x, y = q.popleft()
        if x + 1 == m and y + 1 == n:
            print(visited[y][x])
            return

        for d in dir:
            nx, ny = x + d[0], y + d[1]
            if 0 <= nx < m and 0 <= ny < n:
                if visited[ny][nx] == 0 and miro[ny][nx] == '1':
                    q.append([nx, ny])
                    visited[ny][nx] = visited[y][x] + 1


bfs(0, 0)

 

 

 

 

 

풀이

💡 idea

- 가중치 없는 최단경로 문제 👉👉👉 BFS

- 방문 여부를 저장하는 visited에 True/False 값이 아닌 누적 이동 횟수를 저장

 

 

💡 implementation

- 배열 범위를 벗어나지 않았는지, 방문하지 않은 곳인지, 방문 가능한지('1')

            if 0 <= nx < m and 0 <= ny < n:
                if visited[ny][nx] == 0 and miro[ny][nx] == '1':

 

 

❌ 누적 이동 횟수를 visited에 넣지 않고 queue에 좌표값과 함께 저장했을 때

    * python3으로 돌리면 시간 초과, pypy3으로 돌리면 메모리 초과 발생

from collections import deque
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
miro = []
for i in range(n):
    temp = list(input().rstrip())
    miro.append(temp)

visited = [[False] * m for _ in range(n)]
dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs(x, y):
    q = deque([[x, y, 1]])

    while q:
        x, y, cnt = q.popleft()
        visited[y][x] = True
        for d in dir:
            nx, ny = x + d[0], y + d[1]
            if 0 <= nx < m and 0 <= ny < n:
                if not visited[ny][nx] and miro[ny][nx] == '1':
                    if nx + 1 == m and y + 1 == n:
                        return cnt + 1
                    q.append([nx, ny, cnt + 1])

print(bfs(0, 0))

 

⭕ 누적 이동횟수를 visited에 1씩 증가시키며 저장

visited[ny][nx] = visited[y][x] + 1

 

 

 

 

 

결과