2019.03.19) 소프트웨어 마에스트로 마지막 스퍼트 1편 - 14442 (PyPy3)

2019. 3. 19. 16:21프로그래밍(주력)/백준 문제풀이

오늘은 이상하게 알고리즘 문제가 안풀린다.

그리고 이젠 시간초를 맞추는 좀 억지스러운 코딩 보단 구현에 목적 두고 코딩할 생각이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from sys import stdin
from collections import deque
 
input = stdin.readline
 
n, m, k = map(int, input().split())
= [list(input()) for _ in range(n)]
dist = [[[0* (k + 1for _ in range(m)] for _ in range(n)]
dx = (-1010)
dy = (010-1)
 
 
def bfs():
    q = deque()
    q.append((000))
    dist[0][0][0= 1
    while q:
        x, y, w = q.popleft()
        if x == n - 1 and y == m - 1:
            return dist[n - 1][m - 1][w]
        for i in range(4):
            nx, ny, nw = x + dx[i], y + dy[i], w + 1
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if dist[nx][ny][w]:
                continue
            if a[nx][ny] == '0':
                dist[nx][ny][w] = dist[x][y][w] + 1
                q.append((nx, ny, w))
            if a[nx][ny] == '1' and nw <= k:
                dist[nx][ny][nw] = dist[x][y][w] + 1
                q.append((nx, ny, nw))
    return -1
 
 
print(bfs())
 
cs