[백준] 16930번 달리기 (python, bfs)

728x90
반응형

www.acmicpc.net/problem/16930

 

16930번: 달리기

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

www.acmicpc.net

from collections import deque

n,m,k=map(int,input().split())
dx,dy=[1,-1,0,0],[0,0,1,-1]
vis=[[-1]*m for _ in range(n)]
a=[list(input()) for _ in range(n)]
x1,y1,x2,y2=map(int,input().split())

q=deque()
q.append((x1-1,y1-1))
vis[x1-1][y1-1]=0
while q:
    y,x=q.popleft()
    if y==x2-1 and x==y2-1:
        print(vis[y][x])
        exit()
    for i in range(4):
        for num in range(1,k+1):
            xx=x+dx[i]*num
            yy=y+dy[i]*num
            if xx<0 or xx>=m or yy<0 or yy>=n: break
            if a[yy][xx]=='#':break
            if vis[yy][xx] == -1:
                q.append((yy,xx))
                vis[yy][xx]=vis[y][x]+1
            elif vis[yy][xx]==vis[y][x]+1: continue #일단 쭉 가본다
            else: break # 더 큰길은 탐색하지 않는다

print(-1)

 

728x90
반응형

'백준' 카테고리의 다른 글

[백준] 14503번 로봇 청소기 (bfs, 시뮬레이션, python)  (0) 2020.10.17
[백준] 14888번 연산자 (python, dfs)  (0) 2020.10.17
[백준] 17086번 아기 상어 2 (bfs, python)  (0) 2020.10.16
[백준] 14226번 이모티콘 (bfs, 파이썬)  (0) 2020.10.16
[백준] 13913번 숨바꼭질4  (0) 2020.10.16
TAGS.

Comments