[BOJ][Python] 백준 2161번: 알고스팟

1일 1PS 21일차!

📚 문제

---

골드 4

• 벽을 부순 횟수를 dp 로 기록해야한다.
• 한 방에 있을 경우를 우선적으로 파악해 실행해야한다.
  • queue 에서 한 방에 있는 경우 appendleft 를 통해 우선적으로 실행되도록 한다.

💡 포인트

---

1. (0, 0) 부터 dfs 를 시작한다.
2. 공간으로 연결된 경우를 우선적으로 검색한다.
3. 벽은 이전 벽을 부순 횟수 + 1 로 카운팅 후 기록한다.

💻 코드

---

from collections import deque

N, M = map(int, input().split())

graph = []

for i in range(M):
    graph.append(list(map(int, input())))

dist = [[-1] * N for _ in range(M)]

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

def bfs(a, b):
    queue = deque()
    queue.append([a, b])
    dist[0][0] = 0

    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= M or ny < 0 or ny >= N:
                continue

            if dist[nx][ny] == -1:
                if graph[nx][ny] == 0:
                    dist[nx][ny] = dist[x][y]
                    queue.appendleft([nx, ny])

                else:
                    dist[nx][ny] = dist[x][y] + 1
                    queue.append([nx, ny])

bfs(0, 0)
print(dist[M - 1][N - 1])