[백준 - Python] 16933 - 벽 부수고 이동하기 3

0. 문제 링크

 

 

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

16933번: 벽 부수고 이동하기 3

---

1. 풀이 방법

 

 

우선은 어떤 조건이 우선순위인지 생각을 했다.

최단거리를 출력하는 것과 벽을 몇 개 부쉈는지가 중요한 조건이라고 생각했다.

BFS 특성상 먼저 도착하는 것이 항상 최단거리이므로 벽을 조건으로 생각을 했다.

따라서 visited 배열을 k + 1로 초기화를 했다.

그렇게 하고, 방문 표시를 현재까지 부순 벽의 횟수를 저장했다.

만약 다음에 동일한 곳을 방문했을 때, 더 적게 부쉈을 경우에 방문한다.

당연히 밤과 낮은 따로 처리했다.

---

2. 코드

 

 

from collections import deque

n, m, k = map(int, input().split())
board = [input().strip() for _ in range(n)]
check = [[k + 1 for _ in range(m)] for _ in range(n)]       # 최대로 부술 수 있는 횟수로 채워 넣음
check[0][0] = 0

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

dq = deque()
dq.append([0, 0, 0])
cnt = 1
day = True      # 낮

while dq:
    for _ in range(len(dq)):        # 이중 루프를 하면 한 칸 간 것과 같음 (!)
        y, x, w = dq.popleft()

        if y == n - 1 and x == m - 1:
            print(cnt)      # 찾았다면 현재의 cnt 값으로 출력함
            exit(0)

        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if 0 <= ny < n and 0 <= nx < m and check[ny][nx] > w:
            # 벽이 아닌 경우 낮이든 밤이든 이동이 가능함
            # 현재 내가 부순 벽의 개수가 더 적을 때
                if board[ny][nx] == '0':
                    dq.append([ny, nx, w])
                    check[ny][nx] = w       # 이동했다면 지금까지 부순 벽의 개수로 변경함
                # 벽인 경우
                elif w < k:     # 지금까지 부순 벽이 최댓값보다 작다면
                    if not day:  # 밤
                        dq.append([y, x, w])        # 그냥 기다림, 기다려도 cnt는 추가됨
                    else:
                        check[ny][nx] = w
                        dq.append([ny, nx, w + 1])      # 부수고 감
    cnt += 1        # inner 루프가 끝나면 한 발자국 걸어간 것
    day = not day       # 낮이면 밤으로, 혹은 그 반대
print(-1)

---

3. 마무리

 

 

처음에는 밤일 경우, 기다렸다가 낮이 되어서야 부술 수 있다는 조건을 그냥 밤이면 부수고, 다시 밤으로 만들자라고 생각했다.

근데 스터디 할 때 들으니까 그렇게 하면 BFS의 조건이 깨진다고 한다.

사실 이해는 잘 안되는데, 그냥 그러려니 했다.