[Baekjoon] 2178번 : 미로 탐색 (Python)

[Baekjoon] 2178번 : 미로 탐색 (Python)

 

목차

 

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

2178번: 미로 탐색

Python

 

방법 1 - 메모리 32468KB / 시간 124ms / 코드 길이 789B

 

초기 DFS를 활용한 방법을 사용하였으나 주변부에 대한 update를 하는데 어려움이 존재하였다.

이에 BFS를 통한 주변 업데이트를 한 번에 처리하는 방식으로 탐색을 진행하였다. 

 

 

from collections import deque
import sys
input = sys.stdin.readline

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

visit = [[0]*m for _ in range(n)]

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

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

    while q:
        x,y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx > n - 1 or ny < 0 or ny > m - 1:
                continue

            if visit[nx][ny] != 0:
                visit[nx][ny] = min(visit[nx][ny], visit[x][y] + 1)

            if l[nx][ny] and visit[nx][ny] == 0:
                q.append((nx,ny))
                visit[nx][ny] = visit[x][y] + 1

bfs(0,0)
print(visit[n-1][m-1])

 

방법 2 - 메모리 32452KB / 시간 104ms / 코드 길이 600B

 

방법 1을 간소화한 방법으로 이 방법이 더 빠르고 짧다.

graph를 의미하는 l list에 바로 업데이트하는 방식을 다루고 있다.

 

 

from collections import deque
import sys
input = sys.stdin.readline

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

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

def bfs(x,y):
    q = deque()
    q.append((x,y))

    while q:
        x,y = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx > n - 1 or ny < 0 or ny > m - 1:
                continue

            if l[nx][ny] == 1:
                q.append((nx,ny))
                l[nx][ny] = l[x][y] + 1

bfs(0,0)
print(l[n-1][m-1])