[백준] 1074번 : 미로 탐색 (🥈실버 1) (Python)

문제 바로 가기

1074번: Z

 

---

풀이

• 사용 언어 : Python
• 풀이한 날짜 : 2024-01-11

 

from collections import deque

n, m = tuple(map(int, input().split()))

grid = [
    list(map(int, input()))
    for _ in range(n)
]

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

q = deque()

drs = [0, 1, 0, -1]
dcs = [1, 0, -1, 0]


def in_range(r, c):
    return r >= 0 and r < n and c >= 0 and c < m


def bfs():
    while q:
        r, c, num = q.popleft()

        for dr, dc in zip(drs, dcs):
            nr, nc = r + dr, c + dc
            if in_range(nr, nc) and grid[nr][nc] and not dist_grid[nr][nc]:
                dist_grid[nr][nc] = num
                q.append((nr, nc, num + 1))


q.append((0, 0, 2))
bfs()

print(dist_grid[n - 1][m - 1])

 

풀이 로직

• 가중치가 1인 2차원 배열에서는 BFS 탐색으로 최단 이동 경로(및 거리)를 구할 수 있다.
• (1, 1)에서부터 상하좌우를 살펴보며 너비 우선 탐색을 진행한다. 이 때 이동 가능한 곳으로만 이동해야 하며, 한 번 다음으로 이동할 때마다 거리값을 1씩 증가시켜 나간다.

 

문제 접근 과정 및 느낀점

이 문제 또한 최근에 열심히 연습했던 유형이라 빠르게 문제를 해결할 수 있었다. 다만 초기 조건을 설정할 때 조금 어러움이 있었는데, 이 부분은 계속해서 반복 연습하다 보면 충분히 보완할 수 있으리라 생각한다.