[백준/Python] 1261번: 알고스팟

📁 문제

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

---

💭 풀이

① 빈방 - 자유롭게 다님
② 벽 - 부수지 않으면 이동 X
③ 여러 명이 다른 방에 있을 수 없음
④ 미로 밖으로 이동 X
⑤ (1, 1)과 (N, M)은 항상 뚫려있음

🧡 현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하기 위해 부숴야하는 벽의 최소 개수

0 → 빈방
1 → 벽

벽 = 가중치
탐색하면서 가중치가 적은 경로 찾기 = 부숴야하는 벽의 최소 개수
가중치가 적은 경로를 찾는 문제에는 DFS보다 BFS가 적합하다.

참고: https://devuna.tistory.com/32

0이면 큐의 앞부분에 추가
1이면 큐의 뒷부분에 추가 (가중치 + 1)

• 0 → 0 : 가중치 0
  0 → 1 : 가중치 1
  1 → 1 : 가중치 1

큐에 값이 존재할 동안 상하좌우로 반복

---

🤍 코드

from collections import deque

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

dist = [[-1] * m for _ in range(n)] # 가중치
dist[0][0] = 0  # 첫 가중치
q = deque()
dx = [-1, 1, 0, 0]  # 좌우 좌표배열
dy = [0, 0, -1, 1]  # 상하 좌표배열
q.append([0,0])

while q:
  x, y = q.popleft()
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if 0 <= nx < n and 0 <= ny < m:
      if dist[nx][ny] == -1:
        if maze[nx][ny] == 0:       # (nx, ny)위치의 노드가 0이면
          dist[nx][ny] = dist[x][y] # 이전 가중치 그대로 가져옴
          q.appendleft([nx,ny])     # 큐의 앞부분에 추가
        else: # 1이면
          dist[nx][ny] = dist[x][y] + 1 # 이전 가중치에서 1 증가
          q.append([nx,ny])             # 큐의 마지막에 추가

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