[BOJ] 백준 16933 벽 부수고 이동하기 3 python

무작정 큐에 집어넣는게 능사가 아니고 어떤 조건에서 넣어야하는지 항상 판단할 것.

이렇게 풀면 언어의 한계로 통과되지 않음. 아래 다른 분이 푸신 것을 참고해서 풀 것

https://rebas.kr/799

BOJ 16933 · 벽 부수고 이동하기 3

 

import sys
from collections import deque
def solution():
    """ 이 풀이가 틀린 풀이는 아니지만 언어의 한계로 시간초과가 난다."""
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    MAP = [list(map(int, ' '.join(input()).split())) for _ in range(N)]
    visited = [[[[0,0] for _ in range(K+1)] for _ in range(M)] for i in range(N)]
    q = deque()
    q.append((0, 0, K, 0))

    visited[0][0][K][0] = 1
    moves = [(1,0),(0,1),(-1,0),(0,-1)]
    
    while q:
        r, c, hammer, d = q.popleft()

        if (r, c) == (N-1, M-1):
            return visited[r][c][hammer][d]
        nd = 0 if d == 1 else 1    
        for dr, dc in moves:
            nr, nc = r+dr, c+dc
            
            if nr < 0 or nr >= N or nc < 0 or nc >= M:
                continue

            if MAP[nr][nc] == 1 and hammer != 0 and not visited[nr][nc][hammer-1][nd]:
                if not d:
                    visited[nr][nc][hammer-1][nd] = visited[r][c][hammer][d] + 1
                    q.append((nr, nc, hammer-1, nd))
                else:
                    visited[r][c][hammer][nd] = visited[r][c][hammer][d] + 1
                    q.append((r, c, hammer, nd))
            if not visited[nr][nc][hammer][nd] and MAP[nr][nc] != 1:
                visited[nr][nc][hammer][nd] = visited[r][c][hammer][d] + 1
                q.append((nr, nc, hammer, nd))
    return -1

print(solution())

 

2021/02/26

eia51님이 조언해주셔서 아래와 같은 방법으로 풀 수 있는 것도 알았다. 하지만 댓글은 무례해서 지웠다. 

고맙다 최고다 eia51아 덕분에 하나 배웠다

import sys
from collections import deque

input = sys.stdin.readline

n, m, k = map(int, input().split())

if n == m == 1:
    print(1)
    exit()

road = [[c for c in input()] for _ in range(n)]

visited = [[k + 1 for _ in range(m)] for _ in range(n)]
visited[0][0] = 0
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
q = deque([(0, 0, 0)])
res = 1

is_night = False
while q:
    q_length = len(q) 
    for _ in range(q_length):
        r, c, w = q.popleft()
        
        if r == n - 1 and c == m - 1:
            print(res)
            exit()

        for dr, dc in directions:
            nr = r + dr
            nc = c + dc
            if not(0 <= nr < n and 0 <= nc < m):
            	# 맵의 범위를 벗어난다면
                continue
                
            if visited[nr][nc] <= w: 
	            # 이미 더 적은 방법으로 도달할 수 있다면
                continue
			
            # 밤이 아니고
            if not is_night:
                if road[nr][nc] == '0': # 갈 수 있는 길이라면
                    visited[nr][nc] = w
                    q.append((nr, nc, w))
                else:
                    if w >= k: 
                        continue
                    visited[nr][nc] = w
                    q.append((nr, nc, w + 1))
            else:
                if road[nr][nc] == '0':
                    visited[nr][nc] = w
                    q.append((nr, nc, w))
                else:
                    q.append((r, c, w))

    is_night = not is_night
    res += 1
print(-1)