16930 달리기

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

#bfs

16930번: 달리기

 

#16930 달리기

#16930 달리기

 

#1

 

import sys

input=sys.stdin.readline

def bfs():

    queue=[start]
#queue에 시작점 넣기
    
    curtime=0
#현재 시간 curtime
    
    mintime[start[1]][start[0]]=0
#최소 시간 리스트에서 시작점으로 가는 시간은 0초이다.
    
    dx=[0,0,-1,1]
    dy=[1,-1,0,0]
#dx,dy 4방향 리스트

    while queue:
#queue 돌리기
        
        nextqueue=[]
#nextqueue 새로운 리스트 (queue를 돌리기 때문에 nextqueue 리스트로 갱신해야 중간에 queue 돌릴때 충돌을 안함)
        
        curtime+=1
#현재시간+1
        
        for i in queue:
            x,y=i
#지금 탐색하고 있는 x,y
            
            for i in range(4):    
                for j in range(1,k+1):
                    nx,ny=x+(dx[i]*j),y+(dy[i]*j)
#4방향을 탐색, 최대 k까지 탐색
                    
                    if nx<0 or nx>=m or ny<0 or ny>=n or gym[ny][nx]=="#":
                        break
#조건을 넘거나 벽일경우 스톱
                    
                    if -1!=mintime[ny][nx]<curtime:
                        break
#여기서 중요함, curtime보다 탐색하는게 낮을 경우 이전에 그 위치를 탐색헀다는 말이지? 그럼 그 위치에서
#4방향을 전부 이미 탐색했을껀데, 그 위치에 있는 시간 +1(움직이는 시간 1초) 초으로 4방향에서 최대 k의 거리를 다 탐색을 했다는 말이지? 그럼 더이상 탐색할 필요 없다는것.

                    if -1!=mintime[ny][nx]:
                        continue
#위 코드의 예외사항이라고 생각하면 됨, 크거나 같은 경우 ( 근데 사실 우리는 시간대를 같이 가고 있는 BFS(curtime)를 #사용하기 때문에 같은 경우만 있다고 보면 된다.) 그 이전에 있던거로는 지금보다 더 큰 시간을 소모해서 움직였을꺼기#때문에 다음으로 넘어간다.
                    
                    if mintime[ny][nx]==-1:
                        mintime[ny][nx]=curtime
                        nextqueue.append((nx,ny))
#한번도 탐색되지 않았다면 탐색시간을 저장하고 nextqueue에 집어넣는다.
                    
        queue=nextqueue
#넥스트 큐로 갱신
        if mintime[end[1]][end[0]]!=-1:
            break
            
    return mintime[end[1]][end[0]]
#리턴은 end를 기준으로 한다.

n,m,k=map(int,input().split())
#n*m 크기의 체육관과 최대 k까지 움직일 수 있음

gym=[list(input()) for i in range(n)]
#체육관 생성 "#"은 벽 " . " 은 빈 칸

a=list(map(int,input().split()))
start,end=(a[1]-1,a[0]-1),(a[3]-1,a[2]-1)
#시작점과 끝점

mintime=[[-1 for i in range(m)] for i in range(n)]
#탐색 리스트

print(bfs())

 

#여기까지 내 코드로 열심히 해봤으나 시간이 너무 오래걸렸다. python 으로 통과는 되었으나 4000ms대였고 결국 다른 코드를 살펴보게 된다.

 

#여기서 알게된 것. 끝점과 시작점을 알게 되었을때 시작점부터 끝점까지 bfs를 펼치는것 보다 시작점과 끝점을 동시에 #펼쳐서 둘이 만나면 리턴하는 방식이 훠어어어얼씬 빠르다는 것.

 

#2
import sys
input=sys.stdin.readline

#빠른 입력

n,m,k=map(int,input().split())
gym=[input() for i in range(n)]
x,y,p,q=map(int,input().split())
x-=1
y-=1
p-=1
q-=1
#입력

dx,dy=[0,0,-1,1],[1,-1,0,0]
#4방향

visited=[[[0 for i in range(m)] for j in range(n)] for k in range(2)]
#시작점으로 시작하는 visited 끝점으로 시작하는 visited 각각의 인덱스를 부여해줌 시작점 k=0 끝점 k=1

 

count=[0,0]
#시작점으로 시작한 count 끝점으로 시작한 count

index=0
#0이면 시작점 1이면 끝점

answer=float('inf')
#answer는 최댓값으로 해야 최솟값을 구하기 쉬워짐(min함수로)

queue=[[(x,y)],[(p,q)]]
#queue의 각 인덱스에 시작점 끝점 넣어줌

 

flag=False
#답을 찾으면 True가 될 flag

while queue[index]:
    nextqueue=[]
#index 돌려줌

    count[index]+=1
#일단 시간이 지났으니 1올려주고

    for i,j in queue[index]:
        if visited[index^1][i][j]:
            flag=True

            answer=min(answer,visited[index][i][j]+visited[index^1][i][j])

            break

#만약 뽑아낸 것이 반대쪽점에도 시작한 것에도 탐색완료된거라면 시작점과 끝점으로 시작한 bfs가 서로 만난         

거기에 찾은 것이다.

        for d in range(4):
            for _ in range(1,k+1):
                x=i+dx[d]*_
                y=j+dy[d]*_
                if x<0 or x>=n or y<0 or y>=m or gym[x][y]=='#':
                    break
                elif 0!=visited[index][x][y]<count[index]:
                    break
                elif 0!=visited[index][x][y]:
                    continue

#위 코드와 같이 4방향 k 최대 거리 각각 돌리고 조건 안 맞으면 빼고 중간에 탐색된거 있는데 일찍 한거면 멈추고 같으면 다음꺼로 넘기고 ㅇㅇ

                visited[index][x][y]=count[index]
                nextqueue.append((x,y))
#다 통과하면 count로 설정해주고 nextqueue에 저장해줍니다.    

    if flag:
        print(answer)
        exit()
#답을 찾았다면 답 내고 끝내세요

    queue[index]=nextqueue
#queue[index] 갱신

    if len(queue[index])==0:
        break
#nextqueue가 없으면 break (bfs의 가지가 남아있지 않은 것)

    if len(queue[0])<len(queue[1]):
        index=0
    else:
        index=1
#queue의 각 길이에 따라서 적은 거로 index를 고른다.

 

print(-1)

#답 변

 

#1600초 대로 되더라 이 생각이 참 중요한 듯, 아이디어를 다른 사람 머리에서 가져온거라 아쉽긴 하지만 그래도 수정과 수정 끝에 최적화가 완료된 것 같다. bfs도 다 같은 bfs가 아니라는 생각이 들었던 문제, 시작점과 끝점을 동시에 보는 것은 추후에도 도움이 될 것 같다.