[Python/파이썬] 백준 16933번: 벽 부수고 이동하기 3

문제

 

풀이

n, m, k = map(int, input().split())
graph = [input().rstrip() for _ in range(n)]
visited = [[k + 1 for _ in range(m)] for _ in range(n)]
visited[0][0] = 0

 

visited는 도착했을 때 벽을 부순 횟수를 넣는다.

초기 값으로 벽을 최대로 부술 수 있는 횟수를 넣는다.

 

만약 (x, y) 좌표에서 벽을 부순 횟수(w)가 5번이고, k+1 = 7이라고 가정했을 때

visited[y][x] = 4 인 경우 (x, y) 좌표에 벽을 4번 부수고 방문했다는 뜻

visited[y][x] = 7인 경우 (x, y) 좌표를 아직 방문하지 않았다는 뜻

 

코드

from collections import deque
import sys
input = sys.stdin.readline

def bfs(start):
    q = deque()
    q.append(start)
    ans = 1
    time = True
    while q:
        for _ in range(len(q)):
            i, j, w = q.popleft()
            
            if i == n - 1 and j == m - 1:
                print(ans)
                return
            
            for dy, dx in dir:
                ni, nj = i + dy, j + dx
                if ni < 0 or ni >= n or nj < 0 or nj >= m or visited[ni][nj] <= w:
                    continue
                #벽이 아닌 경우 낮이든 밤이든 이동 가능
                if graph[ni][nj] == '0':
                        q.append((ni, nj, w))
                        visited[ni][nj] = w
                #벽인 경우
                elif w < k:
                    if not time: #밤 인 경우
                        q.append((i, j, w))
                    else:
                        visited[ni][nj] = w
                        q.append((ni, nj, w + 1))
        ans += 1
        time = not time
    print(-1)
    return

n, m, k = map(int, input().split())
graph = [input().rstrip() for _ in range(n)]
visited = [[k + 1 for _ in range(m)] for _ in range(n)]
visited[0][0] = 0

dir = ((1, 0), (-1, 0), (0, 1), (0, -1))

bfs((0,0,0))

 

마무리

풀다가 모르겠어서 구글링 했는데... 생각보다 쉬운 문제여서 허탈했다.

너무 깊게 생각했나 싶기도 하고, 구체적인 부분을 많이 놓친 것 같기도 하다.

아직 골드 1의 난이도는 조금 무리인 것 같다...