[백준] 16930 달리기 파이썬

문제

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

16930번: 달리기

 

진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다.

매 초마다 진영이는 위, 아래, 오른쪽, 왼쪽 중에서 이동할 방향을 하나 고르고, 그 방향으로 최소 1개, 최대 K개의 빈 칸을 이동한다.

시작점 (x1, y1)과 도착점 (x2, y2)가 주어졌을 때, 시작점에서 도착점으로 이동하는 최소 시간을 구해보자.

입력

첫째 줄에 체육관의 크기 N과 M, 1초에 이동할 수 있는 칸의 최대 개수 K가 주어진다.

둘째 줄부터 N개의 줄에는 체육관의 상태가 주어진다. 체육관의 각 칸은 빈 칸 또는 벽이고, 빈 칸은 '.', 벽은 '#'으로 주어진다.

마지막 줄에는 네 정수 x1, y1, x2, y2가 주어진다. 두 칸은 서로 다른 칸이고, 항상 빈 칸이다.

출력

(x1, y1)에서 (x2, y2)로 이동하는 최소 시간을 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

제한

• 2 ≤ N, M ≤ 1,000
• 1 ≤ K ≤ 1,000
• 1 ≤ x1, x2 ≤ N
• 1 ≤ y1, y2 ≤ M

 

 

---

풀이

 

보통 행은 y 열은 x로 쓰지 않나..!

이 문제는 반대여서 중간에 다 뜯어고쳤다.

 

from collections import deque

n, m, k = map(int, input().split())
gym = [list(input()) for _ in range(n)]
time = [[-1]*(m) for _ in range(n)]
sx, sy, ex, ey = map(int, input().split())
sx -= 1
sy -= 1
ex -= 1
ey -= 1

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

time[sx][sy] = 0
q = deque([(sx, sy)])

while q:
    x, y = q.popleft()
    if x == ex and y == ey:
        print(time[x][y])
        exit()

    for d in dir:
        for i in range(1, k+1):
            dx = x + d[0]*i
            dy = y + d[1]*i

            if dx < 0 or dx >= n or dy < 0 or dy >= m:
                break
            if gym[dx][dy] == '#':
                break
            if time[dx][dy] == -1:
                time[dx][dy] = time[x][y]+1
                q.append((dx, dy))

print(-1)

97퍼에서 시초 뜨는 코드

 

 

 

from collections import deque
input = __import__('sys').stdin.readline

n, m, k = map(int, input().split())
gym = [list(input()) for _ in range(n)]
time = [[-1]*(m) for _ in range(n)]
sx, sy, ex, ey = map(int, input().split())
sx -= 1; sy -= 1; ex -= 1; ey -= 1

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

time[sx][sy] = 0
q = deque([(sx, sy)])

while q:
    x, y = q.popleft()

    for d in dir:
        for i in range(1, k+1):
            dx = x + d[0]*i
            dy = y + d[1]*i

            if dx < 0 or dx >= n or dy < 0 or dy >= m:
                break
            if gym[dx][dy] == '#':
                break
            if time[dx][dy] != -1 and time[dx][dy] <= time[x][y]:
                break
            if time[dx][dy] == -1:
                time[dx][dy] = time[x][y]+1
                q.append((dx, dy))

print(time[ex][ey])

readline sys에서 가져오고 중간에 

if time[dx][dy] != -1 and time[dx][dy] <= time[x][y]:

이 조건문 넣고 pypy3로 넣었더니 통과함

 

근데 중간 조건문은 이해가 안간다.

만약에 현재위치 이고 time이 아래와 같을 때

1 2 2

4 4 4

1 -1 1

 

이런 상태면 어떻게 처리되는거지

 

 

+) 오타 못찾고 헛짓거리하다 영진오빠가 찾아줬다ㅎㅎ ㄳㄳ!