19238 - 스타트 택시

처음에 택시와 가장 거리가 가까운 승객을 찾는 함수인 saveDistance를 승객별로 BFS를 실행시켜 구했다.

그렇게 하면 역시나 시간초과가 난다.

 

이전에도 몇번 이런식으로 풀었던거 같은데 한 그래프 안에 2개 이상의 위치에 대한 각각의 최소 거리를 구하거나, 횟수를 구할때는 한번의 BFS로 동시에 구할 수 있다. 이런 생각을 하지 못하다가 힌트를 얻기 위해 여기저기 블로그를 찾다가 이에대한 힌트를 얻었다.

 

saveDistance가 처음에 짰던 그래프 상의 최소 거리를 구하는 함수이다. 그리고 saveDistanc2가 한번의 BFS만으로 어떤 위치든 벽을 제외한 모든 곳의 특정 위치로부터의 거리를 구할 수 있는 함수이다.

 

saveDistance의 경우에는 승객과 택시와의 최소 거리를 모두 구해 어느 승객이 택시에서 가장 가까운곳에 있는지 구하는 함수이고, saveDistance2의 경우에는 승객위치에서 목적지까지의 거리를 구하는 함수이다.

 

* saveDistance 하나로 구현가능할 것 같은데 곧 출근 시간대라 여기까지 하는 것으로 하고 내일 더 다듬어봐야겠다.

# 손님을 도착지로 데려다줄 때마다 연료 충전, 연료가 바닥나면 업무 종료

# M명의 승객이 목표 : 한 승객만 태워 목적지로 이동시키는 일을 M번
# 택시가 빈칸에 있을 떄, 상하좌우로 인접한 빈칸 중 하나로 이동 가능 - 최단경로로 이동
# 현재 위치에서 최단거리가 가장 짧은 승객을 선택 : 여러 명인 경우에는 행 번호가 가장 작은 승객 : 그 다음은 열 번호가 가장 작은 승객
# 택시와 승객이 같은 위치에 있으면 최단거리는 0
# 한 승객을 목적지로 성곡적으로 이동시킨 경우, 소모한 연료의 두배가 충전됨
# 이동하는 중에 연료가 바닥나면 이동에 실패하고, 업무 종료 (목적지 이동 성공과 동시에 연료가 바닥나는 경우는 실패로 간주하지 않음)

N, M, fuel = map(int, input().split())
graph = []
for i in range(N):
    graph.append(list(map(int, input().split())))

taxi = list(map(int, input().split()))
taxi  = list(map(lambda x:x-1, taxi))

customerLoc = []; customerDestination = []
for i in range(M):
    tmp = list(map(int, input().split()))
    customerLoc.append([tmp[0]-1, tmp[1]-1])
    customerDestination.append([tmp[2]-1, tmp[3]-1])

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
from collections import deque
import heapq

# 승객별 BFS 수행 - 시간초과
def saveDistance(taxi, destination):
    visited = [[-1 for _ in range(N)] for _ in range(N)]
    visited[taxi[0]][taxi[1]] = True
    q = deque([[taxi[0], taxi[1], 0]])
    while q:
        x, y, n = q.popleft()
        if [x, y] == destination:
            return n
        for i in range(4):
            nx = x+dx[i]; ny = y+dy[i]
            if 0<=nx<N and 0<=ny<N and visited[nx][ny] == False and graph[nx][ny] != 1:
                q.append([nx, ny, n+1])
                visited[nx][ny] = True
    return -1

# 한번의 BFS 수행으로 택시와 승객과의 거리 계산
def saveDistance2(taxi):
    distGraph = [[False for _ in range(N)] for _ in range(N)]
    visited = [[False for _ in range(N)] for _ in range(N)]
    q = deque([taxi])
    visited[taxi[0]][taxi[1]] = True
    distGraph[taxi[0]][taxi[1]] = 0
    while q:
        # print(q)
        x, y = q.popleft()
        for i in range(4):
            nx = x+dx[i]; ny = y+dy[i]
            if 0<=nx<N and 0<=ny<N and not visited[nx][ny] and graph[nx][ny] != 1:
                distGraph[nx][ny] = distGraph[x][y]+1
                visited[nx][ny] = True
                q.append([nx, ny])
    return distGraph

def saveMinDistanceCustomrt(dList):
    if -1 in dList:
        return -1
    elif dList.count(min(dList)) > 1:
        candiList = list(filter(lambda x : dList[x] == min(dList), range(len(dList))))
        candiXYList = []
        for idx in candiList:
            candiXYList.append(customerLoc[idx])
        heapq.heapify(candiXYList)
        minDistanceCustomer = customerLoc.index(candiXYList[0])
    else:
        minDistanceCustomer = dList.index(min(dList))

    return minDistanceCustomer

completedCustomer = []; chk = False
while customerLoc:
    # 승객별 최단거리 구하기
    dList = []
    distGraph = saveDistance2(taxi)
    print(taxi)
    print(distGraph)
    for i in range(len(customerLoc)):
        cx = customerLoc[i][0]; cy = customerLoc[i][1]
        dList.append(distGraph[cx][cy])

    # 택시로부터 최단거리에 있는 고객 찾음
    minDistanceCustomer = saveMinDistanceCustomrt(dList)

    # 승객에게 못가는 경우
    if minDistanceCustomer<0:
        chk = True
        break

    # 승객의 목적지 위치
    cd = customerDestination[minDistanceCustomer]
    # 승객 위치부터 목적지까지의 거리의 두배 = 충전되는 연료
    beforeFuel = dList[minDistanceCustomer]
    afterFuel = saveDistance(customerLoc[minDistanceCustomer], cd)

    # 목적지까지 못가는 경우
    if afterFuel < 0:
        chk = True
        break
    fuel -= (beforeFuel+afterFuel)

    if fuel>=0:
        fuel+=(2*afterFuel)
        taxi = cd
        del customerLoc[minDistanceCustomer]; del customerDestination[minDistanceCustomer]

    # 연료가 바닥나서 승객을 성공적으로 모두 태울 수 없는 경우
    else:
        chk = True
        break

if chk == True:
    print(-1)
else:
    print(fuel)

아래는 문제를 이해하면서 그려본 그래프이다.

참고해도 좋을것 같아서 가져왔다!

 

 

미라클 모닝 2주차에 2번째 문제 겨우 완성!

하루 한시간씩이긴 한데 그래도 하루를 알차게 쓸수 있다는 점,

퇴근 후에는 아무것도 하기싫어서 타협하는 경우가 많은데 몸에 익으니 아침이 훨씬 더 잘된다는 점

여러 좋은 점이 있는것 같다. :)

 

이게 언제까지 갈지...