스파르탄 365 3주차 (4) 미로 탐색

3주차

백준 2178번 미로 탐색

문제링크 : https://www.acmicpc.net/problem/2178
참고 : https://gingerkang.tistory.com/40

💡 풀이 전 계획과 생각

• 최소 거리를 구하는 문제이니, bfs로 활용해보자

💡 풀이 (가장 깔끔하다 생각되는)

# 풀이 출처: https://gingerkang.tistory.com/40
from collections import deque
import sys

input = sys.stdin.readline

def bfs():
    q = deque()
    q.append((0, 0))
    distance = [[0] * m for _ in range(n)]
    # 시작 위치 카운트
    distance[0][0] = 1
    cnt = 1

    while q:
        x, y = q.popleft()
        for dx, dy in (-1, 0), (1, 0), (0, -1), (0, 1):
            nx, ny = x + dx, y + dy
            if nx < 0 or nx >= m or ny < 0 or ny >= n:
                continue
            if maze[ny][nx] == '1' and distance[ny][nx] == 0:
                distance[ny][nx] = distance[y][x] + 1
                q.append((nx, ny))

    return distance[n - 1][m - 1]


n, m = map(int, input().split())
maze = [input() for _ in range(n)]

print(bfs())

🧐 막혔던 점과 고민

• visited 배열을 어떻게 활용하면 좋을까
  + 1로 구성되어 있으니 누적하는 배열로 쓰자.

👏🏻 알게된 개념과 소감

• 반복문에서 바로 방향 리스트 선언 후 진행

for dx, dy in (-1, 0), (1, 0), (0, -1), (0, 1):
            nx, ny = x + dx, y + dy

• 누적하는 부분

            if maze[ny][nx] == '1' and distance[ny][nx] == 0:
                distance[ny][nx] = distance[y][x] + 1

🔥 해보고 싶은 것

[ __ ] 앞서 풀었던 문제들을 모두 이 코드처럼 다시 짜보자!